apelserg 14 авг 2015 в 16:00

Влияет ли объём данных на трудоёмкость разработки. Учёт в муравейнике

5 мин

5.1K

Big Data * Алгоритмы * Высоконагруженные системы *

-7

196

Комментарии 196

datacompboy 14 авг 2015 в 16:11

Вообще-то, вы только что доказали, что объём данных _влияет_ на решение.

webkumo 14 авг 2015 в 16:12

Скорее не так: объём данных влияет на архитектуру хранения, а следовательно — на архитектуру (способ) решения.

RPG18 14 авг 2015 в 18:20

Требования к разрабатываемой системе определяют архитектуру системы. Рядом с «большими данными» всегда идут хотелки: обработка объема V занимает не более T единиц времени; система должна потреблять не более X, Y, Z ресурсов и т. д. Нефункциональные требования влияют на сложность архитектуры. Сложность архитектура определяет трудоемкость разработки.

apelserg 14 авг 2015 в 22:58

Вы правы, публикация как раз об этом. Показан подход работы с данными.

Просто с первого захода хочется сразу залезть куда-нибудь в Oracle или Hadoop, которые, кстати, в данном случае, мало чем могут помочь. А до второго или третьего захода не всякий Заказчик дотерпит. Хотя правильное решение может быть очень простым, чтобы выйти на него нужно время.

Количество запланированных заходов — это и есть — плановая трудоёмкость.

Скажите честно — а сколько оплаченных попыток на исследования закладываете в проект вы, когда хотите получить выгодный контракт?

datacompboy 16 авг 2015 в 08:57

Я не закладываю попытки на исследования. Если я не знаю решения — я так и говорю.
Обычно, даже если попытка «неудачная» — она идёт в продакшен, и её хватает дожить до более правильной инкарнации.

apelserg 16 авг 2015 в 12:31

Я это называю «ночной кошмар программиста».

Вы разработали проект, но результат получился «не очень» и вы убеждаете и себя и Заказчика, что лучшего быть не может, или это — из области мэйнфреймов/кластеров.А Заказчик и не спорит и даже кивает головой — типа верит. А через некоторое время появляется человек средних лет, с трёхдневной небритостью и потёртым ноутбуком и берётся через неделю продемонстрировать, как увеличить быстродействие вашей системы на пару порядков. В эту неделю плохо спится.

datacompboy 16 авг 2015 в 13:10

Нет. Если результат не очень — я так и говорю, что не очень.
И да, переделку делаю сам.

Просто часто выходит, что поиск глобального оптимума может потребовать неизвестного времени, поэтому соглашаемся на локальный оптимум ради запуска здесь и сейчас.

RPG 14 авг 2015 в 18:09

Странный подход к подсчёту трудоёмкости — решение может занимать 100 строк кода, но на то, чтобы их получить в конечном виде, может потребоваться несколько лет вдумчивой разработки и тестирования. А можно просто набросать копипастой 1000 строк за 10 минут.

Приведу пример. «Простые» на первый взгляд функции стандартной библиотеки Си вроде strcmp, strstr разрабатывают в glibc уже двадцать лет, и до сих пор совершенствуются.

RPG18 14 авг 2015 в 18:25

На самом деле glibc не показатель. Если вы посмотрите исходный код той же функции memcmp, то увидите разные реализации под разные наборы инструкций.

BuriK666 14 авг 2015 в 18:17

Зачем вам ant_to_cell если один муравей может жить только в одном доме? Можно же в ant_list добавить cell_id.

apelserg 14 авг 2015 в 21:41

Такова структура данных. И она однозначно определяет связь многие-ко-многим.

Это означает, что один муравей может проживать (быть прописанным, как у людей) в нескольких домах, и наоборот, несколько муравьёв может проживать в одном доме.

К сожалению, в автоматически подготовленных тестовых данных, это не учтено, так как решалась тестовая задача на объём данных. Но программа подготовки результатов это конечно же учитывает.

webkumo 15 авг 2015 в 12:19

Вообще-то быть прописанным человек может быть только в одном месте.
Дополнительная возможность регистрации по месту пребывания (неограниченное количество) — это совсем о другом и не даёт пользоваться целым спектром гос. услуг.

НЛО прилетело и опубликовало эту надпись здесь

lair 15 авг 2015 в 14:53

Суть решения — в использовании обычного индексного массива. Для каждого списка создаётся массив размером в миллиард.

Эээ, вы это серьезно? У вас задача на обработку «больших объемов данных», и вы ее решаете, загружая все данные в память? А когда памяти не хватило — просто ее добавили?

(а вот внезапно у вас идентификаторы перестали быть числовыми, и что теперь?)

Объём данных не должен оказывать значительного влияния на трудоёмкость разработки. Основная трудоёмкость разработки, как правило, связана со сложностью алгоритма обработки данных, а не с их количеством. Заранее зная фактический объём данных, достаточно разработать код, который работает на небольших данных, а затем его можно применить к требуемому объёму.

Вот только алгоритм зависит от количества данных. Есть алгоритмы попроще, но помедленнее, есть алгоритмы посложнее, но побыстрее.

Главное, как можно раньше (до начала разработки), определить правильный подход к задаче. Но это вопрос не трудоёмкости, а профпригодности — то есть, матчасть надо изучать заранее, а разрабатывать быстро.

Вы готовы заранее «изучить матчасть» под любую задачу, которая может (а может и не) встретиться вам в вашей разработческой жизни?

apelserg 15 авг 2015 в 18:19

У вас задача на обработку «больших объемов данных», и вы ее решаете, загружая все данные в память? А когда памяти не хватило — просто ее добавили?

Если задача может быть решена простым добавлением памяти — в этом нет ничего плохого, это хорошо. Значит в запасе есть ещё один простой механизм решения.

Внезапно у вас идентификаторы перестали быть числовыми, и что теперь?

Внезапно тип индентификатора измениться не может (бывает конечно, но о-очень редко, как правило из-за взаимного недопонимания с Заказчиком).

Есть алгоритмы посложнее, но побыстрее

Здесь вы меня заинтриговали. Что вы имеете в виду?

lair 15 авг 2015 в 18:54

Если задача может быть решена простым добавлением памяти — в этом нет ничего плохого, это хорошо. Значит в запасе есть ещё один простой механизм решения.

Вопрос в том, как решить вашу задачу, не добавляя памяти.

Внезапно тип индентификатора измениться не может (бывает конечно, но о-очень редко, как правило из-за взаимного недопонимания с Заказчиком).

Я имею в виду, что ваше решение хорошо работает до тех пор, пока идентификаторы числовые. Проблема в том, что это не так часто встречается, как нам хотелось бы. Что вы будете делать в этом случае?

Здесь вы меня заинтриговали. Что вы имеете в виду?

Ну смотрите. Вот есть задачка на нахождение кратчайших путей для всех пар точек в графе (без отрицательных циклов). Ее можно решить алгоритмом Флойда-Уоршола за O(|V|³). А можно взять алгоритм Джонсона, который сложнее (это в реальности сочетание двух разных алгоритмов), но решить задачу за O(|V|²log|V| + |V||E|). Соответственно, в зависимости от соотношения вершин-ребер в графе, и от того, какой алгоритм вы готовы реализовывать, и будет зависеть ваше финальное время выполнения.

Или, скажем, с сортировкой. Есть прекрасная сортировка слиянием, простая, понятная, красивая, с гарантированным временем O(n log n). А есть быстрая сортировка (quick sort), которая, вопреки названию, дает O(n log n) только в среднем случае, а в худшем может дать и O(n²). Казалось бы, почему не использовать всегда сортировку слиянием? А потому, что быстрая сортировка работает in place, с минимальными дополнительными расходами памяти, а сортировка слиянием (в простой своей реализации) требует дополнительно столько же места, сколько сам сортируемый массив.

apelserg 15 авг 2015 в 21:15

Вопрос в том, как решить вашу задачу, не добавляя памяти.

Допустим всё увеличилось в 10 раз. Было 3 списка по миллиарду. Стало 3 списка по 10 миллиардов. А ресурсы остались те-же самые (тот самый одинокий комп).

Такая задача решается достаточно просто.

В существующей программе надо дописать процедуру подкачки (она не видится слишком сложной). И последовательно по миллиарду записей подкачивать данные в оба массива. После каждой подкачки прогоняется файл связей (каждый раз все 10 миллиардов). Всё работает точно так, как реализовано сейчас. Всего 100 итераций подкачки. Для улучшения быстродействия я бы поставил SSD. За ночь, вероятно, подсчёт бы выполнился.

Я имею в виду, что ваше решение хорошо работает до тех пор, пока идентификаторы числовые. (Идентификаторы стали не числовые) Что вы будете делать в этом случае?

Сложнее, но порядок действий примерно такой:

Допустим, имеем не числовые идентификаторы, а GUID-ы. И имеем готовые ссылочно-целостные данные.

Для решения надо подготовить хеш-таблицы, где GUID однозначно сопоставляется с числом (это самая затратная по времени операция, её следует продумать). Затем решаем задачу уже известным способом.
Далее, либо оставляем числовые идентификаторы, или делаем обратное сопоставление.

lair 15 авг 2015 в 22:00

Допустим всё увеличилось в 10 раз.

А если в тысячу?

После каждой подкачки прогоняется файл связей (каждый раз все 10 миллиардов).

Вы утверждаете, что у вас алгоритм — IO-bound. Сколько времени (из 30 минут) занимает проход по файлу связей? Вы увеличиваете это время десятикратно, а затем прогоняете это 100 раз… во сколько раз увеличится время работы алгоритма?

За ночь, вероятно, подсчёт бы выполнился.

А это точно допустимое время выполнения? А точно нет другого способа оптимизировать алгоритм?

Для решения надо подготовить хеш-таблицы, где GUID однозначно сопоставляется с числом (это самая затратная по времени операция, её следует продумать). Затем решаем задачу уже известным способом.

Во сколько раз вы только что увеличили требования по памяти? А, главное, зачем вам сопоставлять гуиды с числами?

apelserg 16 авг 2015 в 09:57

А если в тысячу?

Это теоретические фантазии, а ответ очень простой и лежит на поверхности.

Структура данных, рассмотренная в публикации — реляционная и данных много. Это однозначно указывает на то, что данные взяты из промышленной СУРБД. СУРБД, соответствующих вашим запросам, на текущий момент ещё не разработано (приведите примеры).

Кроме того — данные не могут взяться ниоткуда, тем более реляционные. Так что в природе, задачь соответствующих, заданной структуре и вашим требованиям, просто не существует, потому что не существует таких данных.

А это точно допустимое время выполнения? А точно нет другого способа оптимизировать алгоритм?

Одна ночь — это о-очень хороший результат. Обычно, если удаётся уложиться в это время — дальше уже никто не парится, даже если есть известные пути оптимизации.

А кому действительно нужен реалтайм — тот вынужден платить о-очень много за оборудоване и разработку, и процент успешного выхода не 80/20, а 20/80.

Во сколько раз вы только что увеличили требования по памяти? А, главное, зачем вам сопоставлять гуиды с числами?

Требования по памяти на рабочий процесс не увеличилось, совсем. Так как хэш-индекс (именно о нём идёт речь при сопоставлении GUID-а с числом) придётся готовить заранее. Но, для списочных данных, это очень простой и быстрый процесс, так как все GUID-ы уникальные — об этом позаботится СУРБД из которой данные выгружаются.

Другое дело подготовка хэш-индекса на связной список — скорость поиска в ассоциативном массиве на порядки медленнее, чем скорость обращения по индексу в массиве из примера.

Когда хэш-индексы подготовлены — отлично будет работать пример из публикации.

Чисто теоритически есть ещё подход — разработать хэш-функцию, которая на заданном числовом интервале, даст однозначное уникальное преобразование GUID-а в число. Но, к сожалению, вероятность успешной разработки такой функции равна нулю.

lair 16 авг 2015 в 10:11

Это однозначно указывает на то, что данные взяты из промышленной СУРБД.

Лично мне это никак не указывает. Потому что если вы работаете с СУБД, то совершенно не понятно, зачем вы это делаете не в ней.

СУРБД, соответствующих вашим запросам, на текущий момент ещё не разработано

Что такое «мои запросы»? Триллион строк? Во-первых, SQL Server может это пережить (хотя потребуются оптимизации). А во-вторых, если нет такой реляционной БД, значит, нужна нереляционная.

И это как раз наглядная демонстрация того, что объем данных влияет и на архитектуру, и, как следствие, на трудоемкость.

Одна ночь — это о-очень хороший результат. Обычно, если удаётся уложиться в это время — дальше уже никто не парится, даже если есть известные пути оптимизации.

Я не знаю, что такое «обычно». В одном известном мне российском банке окно обслуживания было 4 часа, и все, что в него не влезало, оптимизировали до тех пор, пока не начинало влезать.

А кому действительно нужен реалтайм — тот вынужден платить о-очень много за оборудоване и разработку, и процент успешного выхода не 80/20, а 20/80.

Вы все еще считаете, что объем данных не влияет на трудоемкость?

Требования по памяти на рабочий процесс не увеличилось, совсем. Так как хэш-индекс (именно о нём идёт речь при сопоставлении GUID-а с числом) придётся готовить заранее. [...] Другое дело подготовка хэш-индекса на связной список — скорость поиска в ассоциативном массиве на порядки медленнее, чем скорость обращения по индексу в массиве из примера. [...] Когда хэш-индексы подготовлены — отлично будет работать пример из публикации.

Я не очень понимаю, что именно вы имеете в виду. Вы не могли бы показать на примере?

Чисто теоритически есть ещё подход — разработать хэш-функцию, которая на заданном числовом интервале, даст однозначное уникальное преобразование GUID-а в число. Но, к сожалению, вероятность успешной разработки такой функции равна нулю.

Вероятность тут ни при чем. Однозначно уникальное преобразование — это уже не хэш-функция, а функция сопоставления. Соответственно, для преобразования 2¹²⁸ в 2³² (ну или 2⁶⁴) такая функция невозможна. А если вы берете «числа» из 128-битной арифметики, то такая функция есть, и это банальное тождественное отображение (identity function).

apelserg 16 авг 2015 в 12:40

Лично мне это никак не указывает. Потому что если вы работаете с СУБД, то совершенно не понятно, зачем вы это делаете не в ней.

Модель данных приведена в публикации на рисунке. Кроме того вы можете сгенерировать тестовые данные (ссылка на утилиту в публикации), загрузить их в СУБД и через день-два получите ответ.

Я не очень понимаю, что именно вы имеете в виду. Вы не могли бы показать на примере?

Плохокодить я не буду. А работа с хэш-таблицами и ассоциативными массивами хорошо описана. Если-бы мне было известно хорошее решение по работе с нечисловыми идентификаторами, то в публикации было бы показано оно.

Вы все еще считаете, что объем данных не влияет на трудоемкость?

Утверждение дано в самом начале публикации «Главное, как можно раньше (до начала разработки), определить правильный подход к задаче». Ещё раз. Это означает, что если на архитектуру и разработку надо затратить, например, 3 месяца — значит 3. А, если через 2 месяца работ выясняется, что всё можно сделать за неделю, то… варианты додумайте сами.

ЗЫ Ваши вопросы перестали быть интересными. Давайте закроем дискуссию. Или переведём её в другой формат (но только чтобы было действительно интересно).

[Close]

lair 16 авг 2015 в 12:48

Плохокодить я не буду. А работа с хэш-таблицами и ассоциативными массивами хорошо описана. Если-бы мне было известно хорошее решение по работе с нечисловыми идентификаторами, то в публикации было бы показано оно.

Ну то есть получается, что вы не знаете (правильного) решения задачи для ситуации с нечисловыми идентификаторами. Ок.

Утверждение дано в самом начале публикации «Главное, как можно раньше (до начала разработки), определить правильный подход к задаче».

А как определить, что подход к задаче — правильный? Откуда вы берете критерии правильности?

lair 16 авг 2015 в 12:55

ЗЫ Ваши вопросы перестали быть интересными. Давайте закроем дискуссию. Или переведём её в другой формат (но только чтобы было действительно интересно).

Меня, конечно, забавляет тот факт, что вы предпочитаете «закрыть дискуссию» вместо того, чтобы подумать, как решить вашу задачу не за O(n) памяти (или хотя бы уменьшить коэффициенты).

apelserg 16 авг 2015 в 14:32

Я вас понимаю: лето, мало статей, скука. Сам от этого страдаю.

У меня есть конструктивное предложение. Вы предлагаете алтернативное моему решение по озвученным вами выше вопросам (пусть оно будет не идеальным). Его мы и рассмотрим (не забудте прислать ссылку на код).

ЗЫ Я уверен, что вас заинтересует моё предложение, поэтому прошу открыть новую ветку для обсуждения.

lair 16 авг 2015 в 14:46

Чтобы предлагать альтернативное решение, нужно определиться с условиями задачи. Меня интересуют вполне конкретные вопросы:

Ваше решение всегда выводит данные только по одному типу муравьев. Так и должно быть, или это его недоработка?
Как именно должен выглядеть результат работы (вывод)?
Как в выводе должны выглядеть результаты для муравьев, живущих в более чем одной клетке (раз уж вы утверждаете, что это возможно)?
Откуда в реальности поступают исходные данные, и до какой степени ими можно манипулировать (напоминаю, что вы утверждали, что данные выгружаются из СУБД)?
Можно ли рассчитывать на то, что идентификаторы (муравьев и клеток) целочисленные и последовательные (в значении contiguous)?

apelserg 16 авг 2015 в 17:12

Ваше решение всегда выводит данные только по одному типу муравьев. Так и должно быть, или это его недоработка?

Можно выбрать любой тип заданием параметра: anthill-makeresult.exe 4 (1- царица, 2 — личинка, 3 — нянька, 4 — рабочий, 5 — солдат)

или в коде — изменить тип по дефолту:

int filtrAntType = 5; // дефолтный фильтр - солдат

Как именно должен выглядеть результат работы (вывод)?

Для простоты и переносимости использован CSV. А подойдёт любой формат, главное чтобы можно было легко осуществлять обмен с СУРБД.

Как в выводе должны выглядеть результаты для муравьев, живущих в более чем одной клетке (раз уж вы утверждаете, что это возможно)?

Отношение многие-ко-многим не накладывает количественных ограничений на связи. Главное чтобы идентификаторы в списках были уникальными и пары идентификаторов в таблице связи были уникальными, но за это отвечает СУРБД или утилита подготовки тестовых данных (просто утилита не перемешивает идентификаторы — пусть это вас не смущает, ни пропуски ни последовательность идентификаторов роли не играют).

Откуда в реальности поступают исходные данные, и до какой степени ими можно манипулировать (напоминаю, что вы утверждали, что данные выгружаются из СУБД)?

Хранятся списки в таблицах СУРБД или в CSV файлах значения не имеет. Вы можете легко подготовить тестовые CSV данные, загрузить их в БД, обработать и оставить там, а можете наоборот, из БД в CSV, обработать, а результат загрузить в БД. Но для сути задачи БД не нужна.

Можно ли рассчитывать на то, что идентификаторы (муравьев и клеток) целочисленные и последовательные (в значении contiguous)?

Данные целочисленные, последовательность и пропуски значения не имеют.

Просто вроде как это уже не интересно. Гораздо интереснее рассмотреть вариант, где целочисленные значения идентификаторов заменены на GUID-ы (или другие нецифровые значения, типа не суррогатных, а смысловых ключей, например «A-001-2015.01.01»)

lair 16 авг 2015 в 19:35

Можно выбрать любой тип заданием параметра: anthill-makeresult.exe 4 (1- царица, 2 — личинка, 3 — нянька, 4 — рабочий, 5 — солдат)

Фиксируем: выводятся данные по муравьям одного типа (передаваемого как аргумент).

Для простоты и переносимости использован CSV.

Меня интересовал не формат файла, а его состав. Я так понимаю, что данные групируются по «регионам» муравейника — ок. Что выводится для каждого муравья?

Отношение многие-ко-многим не накладывает количественных ограничений на связи. Главное чтобы идентификаторы в списках были уникальными и пары идентификаторов в таблице связи были уникальными, но за это отвечает СУРБД или утилита подготовки тестовых данных (просто утилита не перемешивает идентификаторы — пусть это вас не смущает, ни пропуски ни последовательность идентификаторов роли не играют).

Вы не поняли мой вопрос. Как в выводе должны выглядеть муравьи, привязанные к нескольким комнатам? Например, если муравей привязан к нескольким комнатам, и эти комнаты в разных регионах — он должен появиться в группе каждого из этих регионов?

Хранятся списки в таблицах СУРБД или в CSV файлах значения не имеет.

Имеет значение то, насколько мы можем управлять этими списками. Например, могут ли они быть заранее отсортированными по нужному мне параметру?

(и да, я ожидаю ответ «да, могут», потому что я с трудом могу себе представить реальную ситуацию, когда это невозможно)

Данные целочисленные, последовательность и пропуски значения не имеют.

Пропуски очевидно имеют значения, поскольку они влияют на алгоритм (удивительно, честное слово, что вы этого не признаете). Но поскольку вы все равно считаете, что это «не интересно», сойдемся на нечисловых идентификаторах (благо, это универсальное решение), а для предсказуемых результатов возьмем GUID-ы (чтобы не думать, как считать потребление памяти для строк переменной длины).

apelserg 17 авг 2015 в 09:40

Я так понимаю, что данные групируются по «регионам» муравейника — ок. Что выводится для каждого муравья?

Да — группировка по регионам. Для каждого муравья выводятся идентификатор муравья и идентификатор ячейки.

Как в выводе должны выглядеть муравьи, привязанные к нескольким комнатам? Например, если муравей привязан к нескольким комнатам, и эти комнаты в разных регионах — он должен появиться в группе каждого из этих регионов?

Да — в группе каждого региона

Например, могут ли они быть заранее отсортированными по нужному мне параметру? (и да, я ожидаю ответ «да, могут», потому что я с трудом могу себе представить реальную ситуацию, когда это невозможно)

Для целочисленных идентификаторов предварительно сделанная сортировка значения не имеет, так как в индексный массив они будут сохранены в соответствии со значением чилового идентификатора.

Для GUID-идентификаторов сортировка, возможно, может иметь значение, но это будет зависеть от выбранного алгоритма хэширования.

lair 17 авг 2015 в 09:48

Итого:

Всегда выводятся данные по одному типу муравьев (который является аргументом к процессу)
Данные выводятся группами по зонам муравейника, внутри каждой группы выводятся идентификатор муравья и идентификатор его ячейки
Если муравей привязан к нескольким ячейкам, то записи в выводе дублируются (как между группами, так и внутри группы)
Входные данные могут быть предобработаны (отсортированы заданным образом)
Идентификаторы муравьев и ячеек — GUID, идентификаторы типов муравьев и регионов муравейника — байт

Все так?

apelserg 17 авг 2015 в 10:15

Да.

Но я бы не стал слишком увлекаться прикладной частью. Мы ведь пытаемся найти решение некой абстрактной общей задачи. Поэтому вы абсолютно свободны в выборе структуры и формата данных.

lair 17 авг 2015 в 10:30

Понимаете, «абстрактная общая задача» решается абстрактным общим способом: возьмите БД (не важно, централизованную или распределенную) и сделайте джойн (не важно, реляционный или нет). Но у нас-то конкретная прикладная часть: столько-то данных, такие-то предположения, такие-то ограничения, давайте во все это укладываться.

apelserg 17 авг 2015 в 10:55

Я вовсе не возражаю, всё это интересно.

Просто проект, который послужил основой для публикации, завершён. Будет другой проект — будут другие данные и другая структура. Например, условие «идентификаторы типов муравьев и регионов муравейника — байт». Фактически, это очень упрощает задачу. А если это тоже GUID или смысловой ключ или даже всего лишь Int32? При этом, описанный в публикации подход, элементарно вылетает в трубу.

lair 17 авг 2015 в 11:13

При этом, описанный в публикации подход, элементарно вылетает в трубу.

Вот именно поэтому решение, зависящее от «а давайте впихнем все в память» масштабируется плохо (а объем данных, в свою очередь, влияет на трудоемкость).

PS Я, правда, тоже пока не вижу хорошего алгоритма под эту задачу с O(1) памяти и O(n) диска, но, повторюсь, хотя бы коэффициенты уменьшить — уже хорошо.

Mrrl 17 авг 2015 в 12:18

Если возможно создание временных файлов и их внешняя сортировка, то всё решается просто:
— создаём файл со списком муравьёв нужного нам типа;
— сортируем его по ant_list_id;
— сортируем копию ant_to_cell по ant_list_id
— проходимся по отсортированным копиям, получаем список (cell_id, ant_list_id) для муравьёв выбранного типа. Сортируем этот список по cell_list_id.
— сортируем копию cell_list по cell_list_id
— проходимся по двум последним спискам и создаём нужные списки муравьёв.
Всё.
Итого — 4 сортировки, две из которых (ant_to_cell и cell_list) нужно выполнить один раз для всех запросов, и два прохода сопоставления списков.
Осталось найти внешнюю сортировку csv-файла произвольного размера по определённому полю. Есть ли такая на примете (на C#)? Может иногда пригодиться :)

lair 17 авг 2015 в 13:22

Что ж вы палите идею-то?

Mrrl 17 авг 2015 в 13:53

А говорите, что не видите… Так что там с внешней сортировкой?

lair 17 авг 2015 в 13:57

Я не вижу решения с O(1) памяти и O(n) дисковых операций. Любая сортировка файла на диске нарушает либо одно, либо другое (либо оба сразу).

Mrrl 17 авг 2015 в 14:03

А, я понял, что O(n) дисковой памяти. Операций, конечно, O(n*log(n)/log(k))), где k — количество записей, которые можно уместить в память. Правда, эти операции очень медленные — сплошные позиционирования.

lair 17 авг 2015 в 15:10

Не, дисковую память я считаю бесплатным ресурсом, меня интересует объем оперативной памяти (она дорогая) и количество дисковых операций (они медленные).

apelserg 17 авг 2015 в 14:10

Фактически, идея уже спалена, так как проект завершён, а вероятность проведения подобных работ мала. Полезнее приложить силы в нужном направлении.

lair 17 авг 2015 в 15:16

Тогда зачем же вы озвучили свое конструктивное предложение?

apelserg 17 авг 2015 в 15:30

Предложение остаётся в силе. Всё что я предлагаю — подкорректировать вектор усилий. Непонятно, зачем брать структуру, изначально ориентированную, на целочисленные идентификаторы и исследовать её просто заменив эти идентификаторы на GUID-ы. Есть действительно актуальные задачи, странно почему вы их избегаете.

lair 17 авг 2015 в 15:34

Непонятно, зачем брать структуру, изначально ориентированную, на целочисленные идентификаторы и исследовать её просто заменив эти идентификаторы на GUID-ы.

А никто и не собирается брать «структуру, изначально ориентированную», я собираюсь взять описанную задачу с оговоренными мной ограничениями, и решить ее в таком виде.

Есть действительно актуальные задачи, странно почему вы их избегаете.

Потому что разговор шел о задаче в посте, и я не вижу смысла ее подменять.

apelserg 17 авг 2015 в 16:00

Понятное решение. Извините, что я пытался вас переубедить.

apelserg 17 авг 2015 в 12:22

Могу предложить рассмотреть ещё пару задач, которые более интересны (ИМХО) с практической точки зрения.

1. Быстрый поиск в ассоциативном массиве. Так, чтобы было быстрее стандартного поиска хотя бы на пару порядков.

2. Разработать функцию для формирования уникального целочисленного значения на заданном числовом интервале для символьного входного значения. То есть — на вход функции строка — на выходе уникальное число. Тогда вообще без ассоциативных массивов можно обойтись и работать с идентификаторами любых типов, как с целочисленными.

Начальные условия для обоих задач: имеем неограниченные ресурсы (для начала можно сделать такое допущение), надо выжать минимальное время, стремящееся к теоретически возможному. Можно установить дополнительные условия (мы же не магией занимаемся).

lair 17 авг 2015 в 13:26

Не, не интересно.

1. Что такое «быстрый поиск»? Поиск по чему? По ключу? По значению?

2. Проще говоря, идеальная хэш-функция. Теоретически возможна в том случае, когда размеры множеств идентичны, но как вы планируете гарантировать это условие?

apelserg 17 авг 2015 в 14:06

1. Что такое «быстрый поиск»? Поиск по чему? По ключу? По значению?

Универсальный, возможно, ориентированный на рассмтриваемую задачу, если предусмотреть в нём индексирование по прикладным данным.

2. Проще говоря, идеальная хэш-функция. Теоретически возможна в том случае, когда размеры множеств идентичны, но как вы планируете гарантировать это условие?

Практически, такую хэш-функцию можно разработать, если предусмотреть в ней так-же индексирование по прикладным данным.

lair 17 авг 2015 в 15:14

Универсальный, возможно, ориентированный на рассмтриваемую задачу, если предусмотреть в нём индексирование по прикладным данным.

Я еще раз спрашиваю: поиск по ключу или по значению?

Практически, такую хэш-функцию можно разработать, если предусмотреть в ней так-же индексирование по прикладным данным.

… если гарантировать, что размеры множеств идентичны (точнее, размер входного множества не больше размера выходного множества) — тогда да, можно. Внутри, правда, все равно будет хэш-таблица, потому что ничего быстрее хэш-таблиц для этой задачи не придумали (я буду рад, если меня поправят).

apelserg 17 авг 2015 в 15:54

Я еще раз спрашиваю: поиск по ключу или по значению?

Что мешает заложить универсальный

lair 17 авг 2015 в 15:59

Вы это серьезно?

В словаре (построенном на хэш-таблице) поиск по ключу — O(1), дальнейшее ускорение — это микрооптимизации. Если у вас внутри не хэш-таблица, то возьмите хэш-таблицу.

С другой стороны, в том же словаре поиск по значению — O(n), просто в силу специфики структуры данных. И чтобы это оптимизировать, проще всего добавить второй лукап (по факту, сымитировать индексы из БД), а дальше у вас начинается развлечение с поддержанием консистентности всей этой конструкции.

Ничего универсального тут быть не может, это принципиально разные вещи.

apelserg 17 авг 2015 в 16:30

Извините, я конечно погорячился с универсальностью. Вопрос — GUID это ключ или значение? Я буду считать его значением, хотя изначально он является идентификатором, то есть ключом (поправьте как вам удобней, это не принципиально). Значит ключ — целочисленное число.

Если я правильно понял замысел задачи, то всем GUID-ам надо сопоставить ключи, и производить все выборки по ключам. Следовательно надо делать поиск по ключу.

lair 17 авг 2015 в 17:12

Я не очень понимаю, о какой задаче вы говорите, правильно ли вы ее поняли, если учесть, что задачу «быстрого поиска» вы же и озвучили. И в этом случае, никому, кроме вас, не известно, что ключ, а что — значение, и по чему там нужен поиск.

apelserg 17 авг 2015 в 19:02

Вот это место, где вы спрашиваете:

Я еще раз спрашиваю: поиск по ключу или по значению?

Я ещё раз обдумал и пришёл к выводу, что придётся делать поиск и по ключу и по значению. Это нужно для разных функциональных этапов. Смотрите, в задаче существует состояние, когда в списке связи известен GUID (значение), но неизвестен ключ. Здесь однозначно нужен поиск по значению. И есть состояние когда нужен поиск по ключу, чтобы быстро получить значение.

lair 17 авг 2015 в 19:06

Я задавал этот вопрос в рамках поставленной вами задачи «Быстрый поиск в ассоциативном массиве. Так, чтобы было быстрее стандартного поиска хотя бы на пару порядков.». Я понятия не имею, зачем вам это надо, что вы имеете в виду, и о какой задаче вы говорите «в задаче существует состояние».

apelserg 17 авг 2015 в 19:47

Я расчитывал на то, что задача «Быстрый поиск в ассоциативном массиве» вас заинтересовала. Если нет, то зачем же тогда вы продолжили обсуждение этой задачи?

lair 17 авг 2015 в 19:55

Я же вам сразу ответил: я не понимаю, что вы в рамках этой задачи пытаетесь сделать, скорее всего, она не имеет смысла.

apelserg 17 авг 2015 в 20:03

А меня наоборот, заинтересовала как раз эта задача. Если удастся продвинуться, я буду держать вас в курсе.

lair 17 авг 2015 в 20:10

Вы бы хоть объяснили, в чем она состоит.

apelserg 18 авг 2015 в 09:03

Так вы сами раскрыли суть этой задачи «Ничего универсального тут быть не может».
Здесь есть, как минимум, несколько интересных мест, над которыми можно поработать.
Например, «поиск по ключу — O(1)». Предположим, что один проход по ассоциативному массиву в миллиард, равен одной секунде.
Миллиард проходов даст миллиард секунд. Грустно. Но, если к этой задаче подключить архитектуру (например разделить процесс),
то можно значительно улучшить время (интересен так же и вопрос цены на единицу улучшенного времени). И это вовсе не «микрооптимизации», а здравый архитектурный подход.

lair 18 авг 2015 в 09:07

Предположим, что один проход по ассоциативному массиву в миллиард, равен одной секунде.

Что такое «один проход»? Одно обращение по заданному ключу? Где вы такие хэш-таблицы берете, это просто нереальные цифры какие-то.

Но, если к этой задаче подключить архитектуру (например разделить процесс),
то можно значительно улучшить время

К какой задаче? Оптимизации одного обращения или оптимизации миллиона обращений?

apelserg 18 авг 2015 в 09:19

Что такое «один проход»?

«Один проход» — это «лукап» по всему массиву (в миллиард).

К какой задаче? Оптимизации одного обращения или оптимизации миллиона обращений?

Речь идёт об оптимизации миллиарда обращений.

lair 18 авг 2015 в 09:23

«Один проход» — это «лукап» по всему массиву (в миллиард).

Я продолжаю не понимать, что вы пытаетесь сделать. Получить значение по конкретному ключу? Получить все ключи? Получить все значения?

Речь идёт об оптимизации миллиарда обращений.

Эта задача находится за пределами структуры данных. К счастью, сам по себе словарь прекрасно выдерживает параллельные чтения (если нет параллельных записей), поэтому вы можете как угодно оптимизировать доступ к нему.

Mrrl 18 авг 2015 в 09:28

К счастью, сам по себе словарь прекрасно выдерживает параллельные чтения (если нет параллельных записей), поэтому вы можете как угодно оптимизировать доступ к нему.

Когда словарь лежит на диске (а миллиард GUIDов в память не лезет), то с параллельным чтением могут возникнуть сложности. И задача оптимизации параллельных обращений вполне может оказаться частью структуры данных.
Насколько я понял, в задаче GUID — ключ, а численный индекс — значение (для возможности работать в дальнейшем через массив).

lair 18 авг 2015 в 09:32

Когда словарь лежит на диске (а миллиард GUIDов в память не лезет), то с параллельным чтением могут возникнуть сложности.

Когда словарь лежит на диске, там больше одной вещи меняется.

И задача оптимизации параллельных обращений вполне может оказаться частью структуры данных.

В этом случае это просто уже не канонический словарь а.к.а. хэш-таблица + дополнительное значение, а конкретная прикладная структура данных, оптимизированная под конкретный сценарий.

Mrrl 18 авг 2015 в 09:37

Тем не менее, эта структура — потомок словаря, возникший из-за того, что данные перестали помещаться в память. И с точки зрения заказчика — это тот же словарь… Хотя, конечно, с ним лучше бы договориться о более эффективном интерфейсе. Который наверняка будет нарушать принцип Single Responsibility и ему подобные, и из-за этого будет безжалостно отвергнут.

lair 18 авг 2015 в 09:48

С заказчиком лучше вообще ни о чем не договариваться, не его это дело, если вкратце. Заказчику надо, чтобы данные были обработаны из состояния А в состояние Б, а уж какая там структура данных — дело пятнадцатое.

Mrrl 18 авг 2015 в 09:59

Если заказчик — тот, кто будет пользоваться непосредственно моим интерфейсом, то это наше с ним общее дело.

lair 18 авг 2015 в 10:09

Ну, у нас с вами расходится понимание (и отношение) заказчика.

Mrrl 18 авг 2015 в 10:26

Да, тех, кто заказывает библиотеку или SDK, мы чаще называем партнёрами.

lair 18 авг 2015 в 10:14

На самом деле, вот тут уже можно и БД взять (KV-хранилище в нашем случае), честное слово. Там неглупые люди сидели и вылизывали алгоритмы, зачем для частной задачи пытаться их переплюнуть?

Mrrl 18 авг 2015 в 10:18

Именно потому, что они разрабатывали алгоритмы и структуры для общей задачи. А у нас — частная. С конкретным соотношением типов, диапазонов и объёмов данных. И лишние 100 байт на муравья нас могут просто убить.

lair 18 авг 2015 в 10:28

Тем не менее, я бы начинал с того, что смотрел на существующие решения, а потом пытался придумать свое.

apelserg 18 авг 2015 в 10:05

Я продолжаю не понимать, что вы пытаетесь сделать. Получить значение по конкретному ключу? Получить все ключи? Получить все значения?

Рамки требований определяет прикладная задача. Фактически, надо быть готовым ко всему. Все перечисленные варианты придётся рассмотреть.

lair 18 авг 2015 в 10:09

Для разных прикладных задач нужны разные структуры данных, зачем в одну-то все запихивать?

Mrrl 18 авг 2015 в 10:15

Например, чтобы не дублировать данные. И не хранить три списка с одним и тем же триллионом муравьёв в разных форматах для разных задач.

lair 18 авг 2015 в 10:18

Оптимизация по производительности рано или поздно все равно приведет к дублированию данных в том или ином виде. Это компромис между одним и другим.

Mrrl 18 авг 2015 в 10:24

Угу. Компромисс. Со всеми возможными решениями — дублирование данных, оптимизация недублированных данных под самую важную задачу, сбалансированная оптимизация под все известные задачи, оптимизация размера… Любой из вариантов может иметь смысл и оказаться наиболее подходящим. И говорить, что один из них правильный, а остальные — некошерные и еретические, наверное, не стоит.

apelserg 18 авг 2015 в 10:37

Для разных прикладных задач нужны разные структуры данных, зачем в одну-то все запихивать?

Для разных прикладных задач потребуются разные структуры.

lair 18 авг 2015 в 10:36

Как-то так.

На ста миллионах записей (на миллиард у меня нет дискового пространства на рабочей машине, и не уверен, что генератору памяти хватит) показатели приблизительно такие:

обработка всего массива за 4:53 (что в два раза быстрее генерации)
константное потребление памяти в районе 24-30 Мб, если верить таск менеджеру
по его же показаниям IO-подсистема загружена полностью (на этой машине у меня только SSD, так что проверить, как оно будет работать на HDD смогу только вечером)

Соответственно, по коду:

потребление памяти — линейное от количества муравьев нужного типа, ровно один HashSet<Guid>, все прочее — O(1), за исключением записи о муравьях в ячейке, там линейное от максимального количества муравьев в какой-либо ячейке
потребление диска — O(n), каждый файл читается строго один раз
к сожалению, две (из трех) операции чтения идут вперемешку, и в эту же гребенку вписана запись, так что нужно либо устройство с хорошим случайным доступом, либо разнести на три разных

PS Код, конечно, грязный.

Mrrl 18 авг 2015 в 11:01

Интересно. Только LinkedList смущает — не будет ли просто List (причём без пересоздания) эффективнее?

lair 18 авг 2015 в 11:16

Если честно, я не знаю, можете форкнуть и проверить. Это все равно не критичное по производительности место, насколько я понял из своих прогонов.

Mrrl 18 авг 2015 в 16:12

Когда я переписал Parser.cs в своей манере — убрал итераторы, ненужные создания Guid и локальных массивов — время работы уменьшилось с 6:27 до 4:25 (на HDD). Так что, вероятно, скорость диска — не единственная проблема.
Чтение файла ants не трогал — оставил HashSet.
С GitHub я не дружу, поэтому копию Parser.cs выгрузил сюда: www.dropbox.com/s/ythlch51enw9n4j/Parser.cs?dl=0 — если вдруг интересно.

lair 18 авг 2015 в 16:14

Наверняка не единственная. Спасибо за изменения, я посмотрю.

lair 19 авг 2015 в 10:12

Вот бранч с вашими изменениями, можно сравнивать построчно с оригиналом. Я чуть-чуть поправил именование и форматирование в нескольких местах, чтобы то, что не менялось по смыслу, не подсвечивалось.

lair 20 авг 2015 в 09:46

В общем, новая версия. Основной прирост в скорости дало выбрасывание лишнего парсинга (т.е. работа напрямую со строками).

Если по шагам, то картинка выглядела так (все замеры делались на одном и том же массиве данных, идентичные фиксированные входные параметры, SSD, усредненный замер из трех):

Мой оригинальный вариант (baseline): 4:40
Ваш вариант: 3:30
Мой следующий вариант (источники в псевдо-джойне поменяны местами, так радикально проще код и не надо собирать массивы муравьев под каждую ячейку): снова 4:40
Наконец, текущий вариант (парсинг гуидов из строк оставлен только для муравьев, идентификаторы ячеек сравниваются как строки с явным указанием Ordinal): 3:15

Учитывая, что у вас метрики сопоставимые, и тоже обработка идет на уровне строк, мне кажется, можно вполне уверенно сказать, что эти 25% времени (немало!) съедались (ненужным) парсингом гуидов. Что думаете?

Mrrl 20 авг 2015 в 10:01

Похоже на правду. Следующим этапом могло бы быть избавление от лишних new string — сравнение фрагментов char[] напрямую (в C++ я бы использовал memcpy, а есть ли аналоги в C#?); переход от char[] к byte[]; возможно, ручная расшифровка Guid (без проверки корректности). Ещё можно поиграть с размером буферов StreamReader (если он к тому времени не превратится окончательно в FileStream) — а потом перейти к опереждающему асинхронному чтению файлов. Интересно, есть ли способы заранее узнать — какие из этих шагов имеют смысл, а какие будут вредной «преждевременной оптимизацией». Поможет ли здесь профайлер?

lair 20 авг 2015 в 10:05

Я из этого пока пробовал буферы — и на SSD результат фактически ухудшился. На HDD ситуация должна быть другой.

Про выкидывание (для «гуидов») стрингов вообще и работу напрямую с байтами я думал; скорее всего, банальное сравнение байт-массивов подряд будет уже работать достаточно эффективно (в принципе, это то, что и делает StringComparer.Ordinal).

Когда я попытался отпрофилироваться, мне все забили I/O-операции. Наверное, это можно побороть, но я пока забил.

apelserg 20 авг 2015 в 15:41

В общем, новая версия

Правильно ли я понял:

1. Два списка должны быть отсортированны в «неубывающую последовательность» до начала обработки: cells и antsToCells(отсортированный по cells). Это условие лежит в основе работы алгоритма.

2. В память (HashSet) полностью помещается ants, а файлы cells и antsToCells (за счёт строгой последовательности cell-идентификаторов) читаются последовательно один раз, в ходе выполнения ants-цикла.

Вопросы:

1. Во сколько вы оцениваете потребность в памяти (сколько RAM должно быть на компе), чтобы обеспечить обработку миллиарда записей?

2. Как вы будете решать задачу, для 10 миллиардов?

3. 100000000 (сто миллионов) записей (ants, cells, antsToCells), на которых производится текущее тестирование, занимают 14 Гб. Значит миллиард займёт 140 Гб. Допустим есть такой поставщик/источник данных (140 Гб в миллиарде записей). Сможет ли этот поставщик данных поставлять отсортированные данные? А, если нет (сервера опечатаны)? Как вы будете решать такую задачу?

lair 20 авг 2015 в 15:50

Два списка должны быть отсортированны в «неубывающую последовательность» до начала обработки: cells и antsToCells(отсортированный по cells). Это условие лежит в основе работы алгоритма.

Да.

В память (HashSet) полностью помещается ants

Нет, только нужного типа.

Во сколько вы оцениваете потребность в памяти (сколько RAM должно быть на компе), чтобы обеспечить обработку миллиарда записей?

При текущем распределении муравьев приложению потребуется 230-250Мб. В более пессимистическом сценарии (скажем, нам нужна 1/5 всех муравьев) — порядка трех-четырех Гб.

Как вы будете решать задачу, для 10 миллиардов?

Аналогично.

Допустим есть такой поставщик/источник данных (140 Гб в миллиарде записей). Сможет ли этот поставщик данных поставлять отсортированные данные?

Да.

А, если нет (сервера опечатаны)? Как вы будете решать такую задачу?

Скорее всего — через внешнюю сортировку.

lair 20 авг 2015 в 16:00

Как вы будете решать задачу, для 10 миллиардов?

Аналогично.

Хотя не, в пессимистичном сценарии — 10 млрд, 1/5 и больше муравьев нужного типа — с памятью начнутся проблемы (хотя не нерешаемые все еще). Там уже придется балансировать между временем выполнения, памятью на машину и количеством машин (там можно породить занятную сетку скоординированных агентов, чтобы читать данные один раз).

lair 20 авг 2015 в 16:30

Ну или четвертый вариант: взять KV-хранилище побыстрее, и запихнуть муравьев туда. Но тут, уже, конечно, придется и с алгоритмом извращаться (чтобы данные проверялись не по записи, а чанками, чтобы уменьшить накладные расходы на обмен), и скорость все равно упадет как бы не на порядок.

Так что возможно, оправдан пятый вариант: уже наконец поискать коробочное решение на базе map-reduce.

apelserg 20 авг 2015 в 16:45

Скорее всего — через внешнюю сортировку

Например предстоит отсортировать antsToCells размером миллиард. Базовый алгоритм сортировки прост. А во сколько вы оцениваете время выпонения полной сортировки на миллиарде записей?

Примечание: можно сделать допущение, что все необходимые структуры всегда помещаются в память (чтобы пока обойтись без «сетки скоординированных агентов» и «коробочного map-reduce-а»).

lair 20 авг 2015 в 18:29

А во сколько вы оцениваете время выпонения полной сортировки на миллиарде записей?

Если в памяти — то за единицы минут плюс время чтения с диска и записи на диск.

можно сделать допущение, что все необходимые структуры всегда помещаются в память

Тогда это уже не внешняя сортировка.

apelserg 21 авг 2015 в 12:49

Если в памяти — то за единицы минут плюс время чтения с диска и записи на диск

Тогда, не могли-бы вы прокомментировать результаты небольшого теста (код приведён ниже).

Суть теста: цикл в миллиард, имеет вложенный цикл в 10. Ничего не делается (простой инкремент переменной). Комп(Core i5) тратит на вычисление — 6.5 секунд. Следовательно, на выполнение вложенного цикла миллиард в миллиарде, должно быть затрачено 650 миллионов секунд.

Или я где-то принципиально ошибаюсь? И, для выполнения сортировки GUID-ов, вы можете предложить другой принципиальный подход, без вложенных циклов (для antsToCells)?

Код теста:

using System;
using System.Diagnostics;

namespace TimeTestBillion
{
    class Program
    {
        static void Main(string[] args)
        {
            long q = 0;
            Stopwatch t = new Stopwatch();

            t.Start();

            for(int i = 0; i < 1000000000; i++)
            {
                for (int k = 0; k < 10; k++)
                {
                    q++;
                }
            }

            t.Stop();

            Console.WriteLine(string.Format("Time: {0} Value: {1}",t.Elapsed.ToString(@"mm\:ss\.fff"), q));
        }
    }
}

lair 21 авг 2015 в 12:58

Следовательно, на выполнение вложенного цикла миллиард в миллиарде, должно быть затрачено 650 миллионов секунд.

А зачем нужен вложенный цикл «миллиард в миллиарде»?

apelserg 21 авг 2015 в 14:18

А зачем нужен вложенный цикл «миллиард в миллиарде»?

Без организации вложенного цикла не решить задачу сортировки cells и antsToCells по cell. Вы можете предложить алгоритм сортировки без организации вложенных циклов?

lair 21 авг 2015 в 14:24

Вы можете предложить алгоритм сортировки без организации вложенных циклов?

Cортировка слиянием, быстрая сортировка.

Дело не во вложенных циклах, а в алгоритмической сложности. Вы зачем-то меряете решение с алгоритмической сложностью O(n²), хотя известно, что сортировка — это O(n log n).

apelserg 21 авг 2015 в 15:36

Скорее всего — через внешнюю сортировку

А во сколько вы оцениваете время выпонения полной сортировки на миллиарде записей?

Вы зачем-то меряете решение с алгоритмической сложностью O(n2), хотя известно, что сортировка — это O(n log n).

Всё, что я хотел узнать — вашу оценку времени выполнения сортировки cells и antsToCells по cell. Примерно, с большим процентом погрешности, но, все-же, имеющую конкретное числовое значение.

lair 21 авг 2015 в 15:39

Так я же уже сказал, вроде бы: минуты + время работы с диском.

lair 21 авг 2015 в 15:43

Время работы с диском можно оценить по тупой операции копирования, которая для двух этих файлов (по 100М строк) занимает на моем компьютере порядка минуты. Умножаем на десять (линейное же), получаем десять минут.

mird 21 авг 2015 в 13:06

Может все же не брать пузырьковую сортировку, а взять алгоритм сортировки с временем n*log(n)? Например quicksort или mergesort. Тогда у вас не будет 2 вложенных цикла по миллиарду.

lair 21 авг 2015 в 13:19

А вот теперь — печальный факт.

На той же самой машине запускаем MS SQL 2012, девелоперская версия. Загоняем туда (в прямолинейную и тупую структуру данных, эквивалентную нарисованной в посте) по 100 млн муравьев, ячеек и связей (вот только связи там сгенерены ровно по одной на муравья, лень было генератор усложнять); короче говоря, повторяем ту же нагрузку. И сравниваем.

Оптимизированное блаблабла решение выдает ~374K записей (~25Mb) за три с небольшим минуты.

Тупое как валенок решение с использованием MS SQL выдает ~390K записей (~26Mb) за 30 с небольшим секунд.

PS Разница в объемах объясняется разницей стартовых данных, но как мы видим, SQL-ное решение процессит их больше.

mird 21 авг 2015 в 13:21

Честно говоря, я не особенно удивлен результату.

Mrrl 21 авг 2015 в 13:46

Интересно. Она действительно прочитала все 14 гигабайт за 30 секунд? Или её база занимает меньше места?

lair 21 авг 2015 в 13:52

Во-первых, ее база занимала меньше места (бинарное представление данных, в результате 23-24/39 байт на строку против 38/67 у нас).
Во-вторых, за счет индексов можно просто пропускать участки и не читать их.
А в-третьих, я, честно, не знаю. Если верить плану выполнения, там внутри добротное количество оптимизаций, включая параллельное выполнение.

apelserg 21 авг 2015 в 13:50

А вот теперь — печальный факт.

Правильно ли я понимаю, что в MS SQL 2012 вы поместили те-же отсортированные данные, что использовали раньше?

lair 21 авг 2015 в 13:54

Неправильно понимаете. Тут все данные были сгенерены и загружены согласно «типовой» политике первичных ключей, а дальше уже все сортировки и индексацию SQL делал сам.

insert Ants (type)
output inserted.Id into @ant
values (@type) --последовательно увеличивается

insert Cells (area)
output inserted.Id into @cell
values (0) --а это не важно, мог бы и случайный генерить

insert Links
select antId, cellId
from @ant cross join @cell

apelserg 21 авг 2015 в 14:14

Неправильно понимаете. Тут все данные были сгенерены и загружены согласно «типовой» политике первичных ключей

Вы уверены, что приведённый вами фрагмент кода понятен? Есть ли простая возможность использовать ваш генератор?

lair 21 авг 2015 в 14:17

Вы уверены, что приведённый вами фрагмент кода понятен?

Человеку, который умеет читать T-SQL — да, уверен.

Есть ли простая возможность использовать ваш генератор?

Нет, я не делал скрипт БД.

lair 21 авг 2015 в 14:24

Вот скрипты.

apelserg 18 авг 2015 в 16:20

Как-то так

1. Не понимаю смысла формирования GUID-ов разного типа для муравьёв и для ячеек:

(муравьи)
2d9bd55609174c029abc69c6fc2d02c5

(ячейки)
00000000491c61c0d1043fc221c3bff4

2. При подготовке результата (area-071, area-153,… ) всегда присутствует только по одной записи в каждом файле. Это недоработка?

lair 18 авг 2015 в 16:23

Не понимаю смысла формирования GUID-ов разного типа для муравьёв и для ячеек:

Для муравьев можно использовать случайные, а для ячеек удобнее использовать последовательные. Это критично только в генерации, парсер этот факт игнорирует.

При подготовке результата (area-071, area-153,… ) всегда присутствует только по одной записи в каждом файле. Это недоработка?

У меня такого поведения не наблюдается. Какого размера у вас стартовый массив данных?

apelserg 18 авг 2015 в 16:53

для ячеек удобнее использовать последовательные. Это критично только в генерации.

Не понимаю, вы можете пояснить в чём удобство? (По коду я не понял, а комментарии отсутствуют)

У меня такого поведения не наблюдается. Какого размера у вас стартовый массив данных?

Пока 1000. Я устанавливал разные типы (например 255) — результат — всегда одна запись на один файл.

Всего муравьёв типа 255 в файле ants — 273
Файлов на выходе — 35 (area-004, area-009, area-013,… area-218, area-230, area-238)

Это вид консоли:
С:\anthill-guid>AntHeap.Parser.exe .\ .\ 255
Parsing ants of type 255 from .\ to .\
Parsing complete in 00:00.038

lair 18 авг 2015 в 18:00

Не понимаю, вы можете пояснить в чём удобство? (По коду я не понял, а комментарии отсутствуют)

Парсер ожидает, что файлы cells и antsToCell отсортированы по возрастанию идентификаторов ячеек.

Пока 1000. Я устанавливал разные типы (например 255) — результат — всегда одна запись на один файл.

Может быть, это баг (а может — специфика генератора). Вы можете куда-нибудь выложить файлы, которые вы обрабатываете?

Mrrl 18 авг 2015 в 17:05

Для муравьев можно использовать случайные, а для ячеек удобнее использовать последовательные. Это критично только в генерации, парсер этот факт игнорирует

Для парсера важно, что и в файле cells, и в antsToCells имена ячеек идут в лексикографическом порядке (Guid не убывают).

apelserg 18 авг 2015 в 17:23

Для парсера важно, что и в файле cells, и в antsToCells имена ячеек идут в лексикографическом порядке (Guid не убывают).

Если для парсера важно, чтобы GUID-ы были «ненастоящими» и последовательными — такое условие нарушает «чистоту» эксперимента.
GUID-ы, которые на самом деле GUID-ами не являются, в природе не существуют, а если существуют, то это можно рассматривать как «информационное преступление».

Mrrl 18 авг 2015 в 17:49

Если для парсера важно, чтобы GUID-ы были «ненастоящими» и последовательными

Нет, это не важно. Важно, чтобы последовательность была неубывающей.

apelserg 19 авг 2015 в 08:46

Нет, это не важно. Важно, чтобы последовательность была неубывающей.

Вы меня удивляете. Я, например, не вижу абсолютно никакой разницы между понятиями «ненастоящие GUID-ы» и «Важно, чтобы последовательность была неубывающей». Это — «подтасованные данные».

Неужели вас может интересовать результат, полученный на «подтасованных данных»?

lair 19 авг 2015 в 08:51

В чем их подтасованность?

apelserg 19 авг 2015 в 09:19

В чем их подтасованность?

Хорошо, вы утверждаете, что таким образом (используя ненастоящие GUID-ы) имитируете препроцессинг «я не зря спрашивал, разрешен ли препроцессинг». Что вам мешает на этапе генерации провести этот «препроцессинг» на основе «честных» GUID-ов (конечно это немного усложнит генератор).

lair 19 авг 2015 в 09:29

Что вам мешает на этапе генерации провести этот «препроцессинг» на основе «честных» GUID-ов (конечно это немного усложнит генератор).

Я же писал уже: скорость. В предыдущей версии так и было (и код, на самом деле, проще), но скорость генерации падала даже не как n log n от объема.

apelserg 19 авг 2015 в 10:13

но скорость генерации падала даже не как n log n от объема

Я считаю, что задача, фактически, состоит из двух этапов:
1. Подготовка тестовых данных;
2. Подготовка результата;

Вы поторопились приступить ко второму, не разобравшись с первым.

А первый этап (подготовка результатов) уже начинает преподносить свои сюрпризы. Оказывается расчитывать на последовательность данных (препроцессинг) не стоит. Скорее наоборот — препроцессинг невозможен. Или привидите пример, как вы собираетесь выгружать отсортированные данные такого объёма из, например, СУРБД?

lair 19 авг 2015 в 10:19

Скорее наоборот — препроцессинг невозможен.

Почему невозможен-то? Просто он занимает больше времени, чем мне комфортно ожидать в целях тестирования. Я нашел способ заменить его таким образом, чтобы подготовленные данные семантически не отличались от тех, которые подготовлены случайным образом, а затем отсортированы. Собственно, если вы посмотрите в генерацию, то увидите, что массив связей (который состоит из стольких же элементов, что массив ячеек) сортируется без особыз проблем.

Или привидите пример, как вы собираетесь выгружать отсортированные данные такого объёма из, например, СУРБД?

Как-как, по индексу, конечно.

И да, если это проблема, то почему вы согласились с тем, что входные данные могут быть отсортированными?

apelserg 19 авг 2015 в 11:05

Как-как, по индексу, конечно.

Поясните, как это? ORDER BY GUID_ID по таблице в миллиард записей? Как вам удаётся такие индексы строить?

И да, если это проблема, то почему вы согласились с тем, что входные данные могут быть отсортированными?

Я вовсе не соглашался, я просто переубеждать вас не стал. Вы так уверенно взялись за задачу. А вдруг? Зачем же прерывать полёт творческой мысли.

Давайте проводить честный эксперимент и начнём с тех проблем, которые могут возникнуть в реальной жизни (ну пусть немножко виртуальной).

lair 19 авг 2015 в 11:14

ORDER BY GUID_ID по таблице в миллиард записей? Как вам удаётся такие индексы строить?

ORDER BY — это сортировка при выводе. А индекс — это индекс. Обычный такой индекс на БД. А в чем, собственно, проблема?

Я вовсе не соглашался, я просто переубеждать вас не стал.

Ну нет, так не работает. Я явно привел пункт «Входные данные могут быть предобработаны (отсортированы заданным образом)» и спросил «все так», вы явно ответили «да». Если это не согласие, то что — согласие?

Давайте проводить честный эксперимент и начнём с тех проблем, которые могут возникнуть в реальной жизни

Да пожалуйста. Какие проблемы у вас могут возникнуть «в реальной жизни»?

apelserg 19 авг 2015 в 12:52

Обычный такой индекс на БД

Объясняю. Индекс для сортировки не поможет, так как ресурсы, требуемые для запроса-вывода, значительно превышают ресурсы любого мыслимого сервера.

Строить индекс или нет для обеспечения простого несортированного запроса на таком объёме данных? Не буду вводить вас в заблуждение — этот вопрос требует изучения.

Ну нет, так не работает

Браво! Вы меня не перестаёте удивлять! Я честно признался, что красивое решение мне неизвестно. Вы, совершенно добровольно, взялись за задачу (от которой я вас отговаривал), сами сформировали требования (против которых я всего лишь не стал возражать), но задача оказалась не постой (так бывает). Не понимаю, какой ответ вы от меня ожидаете получить? Я повторяю — мне красивого и технологичного решения этой задачи неизвестно (я её конечно же продумывал).

Какие проблемы у вас могут возникнуть «в реальной жизни»?

Пока, возникли проблемы с простой сортировкой списка. Пока не получается найти решения. Это можно «записать в книжечку». По-моему это очень хороший «сухой остаток» и потраченное время нельзя назвать «бессмысленно потраченным».

lair 19 авг 2015 в 12:55

Индекс для сортировки не поможет, так как ресурсы, требуемые для запроса-вывода, значительно превышают ресурсы любого мыслимого сервера.

Ээээ… то есть вывести данные из таблицы можно, а вывести данные из индекса (который сопоставимого размера) — не хватает ресурсов? Но как?

Пока, возникли проблемы с простой сортировкой списка.

В реальной жизни нет проблем с сортировкой списка, потому что в реальной жизни сортировка списка происходит за рамками задачи.

apelserg 19 авг 2015 в 13:16

Ээээ… то есть вывести данные из таблицы можно, а вывести данные из индекса (который сопоставимого размера) — не хватает ресурсов? Но как?
Пока, возникли проблемы с простой сортировкой списка.

В реальной жизни нет проблем с сортировкой списка, потому что в реальной жизни сортировка списка происходит за рамками задачи.

Я перестал понимать ход ваших мыслей. О каких индексах и о каких рамках вы говорите? Сделайте простой сортированный список на GUID-ах и О'кей. Но вы утверждаете, что проблема в скорости. Хорошо, предложите другой подход. Я повторяю — решение этой проблемы мне неизвестно.

lair 19 авг 2015 в 13:21

О каких индексах

О самом обычном индексе в базе данных. Мы же неоднократно обсуждали, что исходные данные приходят, на самом деле, из СУБД.

о каких рамках

О тех, которые описаны в посте. Ведь решаемая задача — это когда есть несколько (больших) источников данных, и их надо обработать по вполне тривиальным правилам. Вот этим мы и занимаемся.

Сделайте простой сортированный список на GUID-ах и О'кей.

Что такое «простой сортированный список на гуидах»? Я не очень понимаю, что там делать.

Но вы утверждаете, что проблема в скорости.

Я утверждаю, что скорость работы генератора тестовых данных при неоптимальном алгоритме меня не устраивала, поэтому я написал более оптимальный алгоритм. Содержимое исходных (для обработчика) файлов от этого не изменилось.

Хорошо, предложите другой подход.

Другой подход к чему?

Я повторяю — решение этой проблемы мне неизвестно.

Какой проблемы?

apelserg 19 авг 2015 в 13:40

Другой подход к чему?
Какой проблемы?

Мммм… Похоже, я перестал понимать, что вы не понимаете. Решите задачу, так как вы сами её понимаете. Наверное это будет самым разумным подходом. Я всегда готов оказать посильную помощь, задавайте любые вопросы.

lair 19 авг 2015 в 13:42

Так уже решил же.

apelserg 19 авг 2015 в 14:06

Так уже решил же

Вы это действительно серьёзно? Вы даже не реализовали сортированного списка тестовых данных для «честных» GUID-ов. Я даже не приступал к тестированию вашего решения на больших данных, потому что это бессмысленно, ваше решение имеет ограничение на размер списка.

lair 19 авг 2015 в 14:13

Конечно, серьезно.

Вы даже не реализовали сортированного списка тестовых данных для «честных» GUID-ов.

Что значит «не реализовал»? Данные на вход парсеру поступают сортированные? Сортированные.

Я даже не приступал к тестированию вашего решения на больших данных, потому что это бессмысленно, ваше решение имеет ограничение на размер списка.

Конечно, имеет, я его даже указал — грубо, это 16*(количество муравьев нужного типа) (плюс накладные расходы на HashSet). На ста миллионах записей вся программа потребляла 23-25Мб в пике. Я считаю, это неплохой показатель.

Как говорилось выше, как сделать за O(1) памяти — я не знаю (точнее, знаю, но это будет дорого по диску, я не берусь сходу оценить сложность).

Mrrl 19 авг 2015 в 14:56

ваше решение имеет ограничение на размер списка.

Всего лишь ещё одно подтверждение того, что объём данных влияет на трудоёмкость. Требование к данным ослаблено до того, чтобы множество идентификаторов для муравьёв выбранного типа помещалось в память; на число комнат и связей «муравей — комната» ограничений уже нет. Если и муравьи перестанут помещаться в память — это будет следующий этап, более трудоёмкий. Когда список муравьёв придётся собирать по всему Интернету — следующий…

apelserg 21 авг 2015 в 12:52

Всего лишь ещё одно подтверждение того, что объём данных влияет на трудоёмкость

ИМХО: Я думаю, что мне бессмысленно продолжать настаивать на своей точке зрения, но и отказываться от неё, я не вижу оснований.
Всякий, кто прочтёт комментарии к публикации, сможет сам определить свою позицию по этому вопросу.

Mrrl 19 авг 2015 в 13:00

Кто вам мешает отсортировать файл в миллиард строк по индексу, записанному в определённом месте каждой строки? Если с этим не справляются базы данных — сортируйте сами, алгоритмы внешней сортировки давно известны. Люди пользовались ими, ещё когда данные были на магнитофонных лентах, а память компьютеров была совсем маленькой. Можно поискать у Кнута, третий том.

apelserg 19 авг 2015 в 13:28

Кто вам мешает отсортировать файл в миллиард строк

Правильно ли я понимаю, что именно этот подход, вызывает затруднение?

lair 18 авг 2015 в 18:02

Если для парсера важно, чтобы GUID-ы были «ненастоящими» и последовательными

Для парсера важно, чтобы строчки в файле были отсортированными определенным образом (я не зря спрашивал, разрешен ли препроцессинг), а уж из каких оно гуидов — не принципиально. Со случайными просто генератор дольше работает.

lair 18 авг 2015 в 18:01

Угу. В первой версии генератора были случайные гуиды и сортировка, но на больших объемах это медленно. Сгенерить сразу возрастающие оказалось намного проще и экономнее.

apelserg 18 авг 2015 в 17:11

Уточнее:

Пока 1000. Я устанавливал разные типы (например 255) — результат — всегда одна запись на один файл.

Всего муравьёв типа 255 в файле ants — 273

Всего муравьёв типа 255 в файле ants — 373 (а не 273)

В 6 файлах из 35 — по 2 записи (в остальных по одной)

Mrrl 18 авг 2015 в 17:48

Тут дело в том, что некоторые муравьи живут в нескольких комнатах сразу (в 1 или 2), а некоторые — нигде не живут (в файле antsToCells столько же строк, сколько муравьёв). Муравьёв, судя по всему, расселяют начиная с младших типов, поэтому заметная часть последних — с типом 255 — оказывается среди бездомных. В среднем, бездомных будет N/3, это примерно 333 муравья из 373 (типа 255). Поселённых окажется около 40, что соответствует вашим результатам.

lair 18 авг 2015 в 18:04

Скорее всего, вы правы. В принципе, чтобы убрать это поведение, достаточно в генераторе убрать «обрезание» списка расселений по максимальной границе (которая одна для всех файлов), но тогда он скорее всего будет где-то 2N строчек.

Собственно, у генератора вообще есть глюки в распределении всяких случайных значений.

apelserg 19 авг 2015 в 08:38

Поселённых окажется около 40, что соответствует вашим результатам

Это понятно (посмотрел код), данные для таблицы связи формируются случайным образом. Но отлаживать функциональную часть удобнее и правильнее на небольшом объёме целостных данных.

lair 19 авг 2015 в 08:52

Данные, на самом деле, целостны — ни одной битой ссылки нет. Но я с удовольствием послушаю про алгоритм, который бы генерил полный набор данных со случайным распределением.

apelserg 19 авг 2015 в 09:37

Но я с удовольствием послушаю про алгоритм, который бы генерил полный набор данных со случайным распределением.

Я вообще не понимаю, зачем вам нужно здесь случайное распределение.

Объясняю. Муравьёв — 1000, ячеек — 1000, связей — 1000. Муравьёв типа 255 — 373. В результате — 40 записей. Вы сдаёте систему. Ни один приёмщик вам акты не подпишет.

lair 19 авг 2015 в 09:41

Я вообще не понимаю, зачем вам нужно здесь случайное распределение.

Потому что придумывать детерминированный алгоритм сложнее.

Муравьёв — 1000, ячеек — 1000, связей — 1000.

… и мы все понимаем, что либо на каждого муравья не больше одной ячейки, либо у каких-то муравьев их больше одного, а у каких-то ни одной. Какой сценарий вам интереснее? Мне кажется, что второй правильнее. Ну и да, превратить второй в первый в моем коде можно изменением одной строчки.

Вы сдаёте систему. Ни один приёмщик вам акты не подпишет.

Ну нет, когда я сдаю систему, есть ПМИ, в которых явно описано, что на входе, что на выходе.

apelserg 19 авг 2015 в 10:41

Какой сценарий вам интереснее? Мне кажется, что второй правильнее.

Я думаю, что было-бы интереснее и правильнее использовать подход, когда для каждого муравья есть ячейка и, некоторые муравьи, могут жить в нескольких ячейках (то есть список связей больше количества муравьёв). Проверить функциональность алгоритма на «бездомных муравьёв» можно даже просто ручным удалением записей на малых данных, а на больших данных смысла проверять нету.

когда я сдаю систему, есть ПМИ

Интересно посмотреть на ПМИ, где прописано, что зависимости получаются случайным образом и не проверяются (где вы таких Заказчиков находите?).

Кроме того, любые требования ТЗ, ПМИ, рабочий план-график и т.д. всегда можно «уточнить». Разве вам не знакома ситуация, когда завтра/на следующей неделе должна сдаваться система,
но к вам подходит ПМ и ставит в известность, что с Заказчиком подписаны «небольшие» изменения, «не влияющие на сроки», которые надо срочно доработать. Иначе контракт закрывается, нет финальной оплаты, прощай премия.

lair 19 авг 2015 в 10:45

Я думаю, что было-бы интереснее и правильнее использовать подход, когда для каждого муравья есть ячейка и, некоторые муравьи, могут жить в нескольких ячейках (то есть список связей больше количества муравьёв).

Окей, на какие множители вы согласны? Исправить-то несложно (собственно, вам и самому ничего не мешает форкнуть и исправить).

Интересно посмотреть на ПМИ, где прописано, что зависимости получаются случайным образом и не проверяются (где вы таких Заказчиков находите?).

Да нет, в ПМИ как раз в норме никаких случайностей нет. Но мы же здесь без ПМИ работаем, правда?

Разве вам не знакома ситуация, когда завтра/на следующей неделе должна сдаваться система,
но к вам подходит ПМ и ставит в известность, что с Заказчиком подписаны «небольшие» изменения, «не влияющие на сроки», которые надо срочно доработать.

В такой ситуации полезно пойти к начальнику и удостовериться, что овертайм разработчиков будет оплачиваться из премиального фонда ПМ. Но это тема совершенно отдельного разговора.

apelserg 19 авг 2015 в 12:48

Окей, на какие множители вы согласны?

Меня устроят любые. Всё, что я делаю — задаю (очень) простые вопросы, а решения по вашей разработке (на которую вы совершенно добровольно согласились) конечно должны принимать вы.

В такой ситуации полезно пойти к начальнику

Вопрос, конечно, не технический, а организационный. Но я бы не стал ходить к начальнику, если, конечно, это не ваш близкий родственник или хороший знакомый. В такой ситуации, приоритет контракта с Заказчиком и наличие мотивированного ПМ-а в этом контракте, для любого начальника, на порядок (или два) выше личного недовольства, пусть даже гениального, разработчика. А ПМ-то чем виноват? В 99% он в той-же шкуре, что и разработчик.

lair 19 авг 2015 в 12:51

Меня устроят любые.

«Любые» уже сделаны. Но они вас почему-то не устраивают.

Окей, предложим другие «любые» — муравей может быть (равновероятно) приписан к одной или двум комнатам, «беспризорников» нет, соответственно, вероятный общий размер файла связей — 1.5N. Устраивает?

В такой ситуации, приоритет контракта с Заказчиком и наличие мотивированного ПМ-а в этом контракте, для любого начальника, на порядок (или два) выше личного недовольства, пусть даже гениального, разработчика.

Я уже сказал — это не тема для обсуждения здесь.

apelserg 19 авг 2015 в 12:57

Но они вас почему-то не устраивают

При подготовке тестовых данных, я исхожу из того, что результат должен быть проверяем.

lair 19 авг 2015 в 12:59

При подготовке тестовых данных, я исхожу из того, что результат должен быть проверяем.

Он полностью проверяем.

apelserg 19 авг 2015 в 13:24

Он полностью проверяем

Вы это называете проверяемостью?

lair 19 авг 2015 в 13:26

Конечно. Для каждой записи в списке связей можно проверить, какого типа в ней муравей, и если он того типа, по которому гоняется тест, проверить, занесен ли он в нужный файл, и указана ли там правильная ячейка.

apelserg 19 авг 2015 в 13:46

Конечно. Для каждой записи в списке связей можно проверить, какого типа в ней муравей, и если он того типа, по которому гоняется тест, проверить, занесен ли он в нужный файл, и указана ли там правильная ячейка.

Я не возражаю

webkumo 16 авг 2015 в 11:31

Простите, не уверен, что понял вас…
— зачем вам построение хеш-индекса? (какие цели в этой теоретической задаче вы преследуете)
— «построение хеш-индекса» — это явно усложнение алгоритма… т.е. архитектура данных обусловленная объёмом данных таки повлияла на алгортим, не так ли?

apelserg 16 авг 2015 в 12:41

Конечно влияет и об этом ясно сказано в публикации «Существенное влияние на решение могут оказать, например, другая структура или другой формат прикладных данных».

Если у вас будут данные, где уникальным идентификатором является произвольная срока, то без хэш-индекса (ассоциативными массива) будет сложно обойтись.

Mrrl 16 авг 2015 в 20:15

Чтобы вычислить индекс по GUID, надо, чтобы эти GUID хранились в явном виде. В памяти. Так что вместо одного байта вам потребуется, по меньшей мере, 17.

apelserg 17 авг 2015 в 09:46

Это вовсе не обязательно и зависит от выбранного подхода.

Например, выбираем подход с хэшированием GUID-ов. На линейные списки хэш вычисляется просто и быстро. Отсортировали, выгрузили список из СУРБД в CSV, а потом отхешировали присвоением GUID-у числового идентификатора по номеру строки (создали новый CSV).

Сложнее сделать следующую итерацию — отхэшировать список связей (сопоставить каждый GUID с уже известным числовым идентификатором). Чем больше данных — тем дольше поиск по ассоциативному массиву (время может вырасти до неприличных значений). Кроме того, если ассоциативный массив не поместился в память, то тут и начинается основное плохокодирование. Мне красивое решение неизвестно.

Mrrl 17 авг 2015 в 12:34

Я бы делал так.
Пусть у нас N GUID'ов. Выберем хэш-функцию, принимающую K=N/500 значений. Вероятность того, что одно значение окажется больше, чем у 700 GUID из набора, очень мала.
Строим K хэш-таблиц на 960 ячеек каждая (по другой хэш-функции), заполняем (номер таблицы для данного GUID находим по первой хэш-функции), записываем в файл прямого доступа блоками по 16 килобайт. Если какая-то таблица переполнилась — пишем ей в хвост ссылку на дополнительный блок (с номером, большим K).
Теперь при поиске находим номер блока, подгружаем соответствующие 16 КБ и ищем наш GUID в соответствующей таблице. Если не нашли — переходим к дополнительному блоку, если он есть.
Да, велосипед. Но не требует подключения никаких баз данных (если в проекте их раньше не было).

lair 15 авг 2015 в 22:25

В существующей программе надо дописать процедуру подкачки (она не видится слишком сложной). И последовательно по миллиарду записей подкачивать данные в оба массива.

Да, кстати. Чтобы это сделать на CSV-файле, вам придется читать все записи до нужной вам (структура файла не позволит вам быстро и дешево пропустить ненужное). Соответственно, на чтение каждого файла (муравьи и клетки) у вас уйдет не 10х времени, а 55х. Вместе с тем, что файл связей вы прогоняете каждый раз целиком, вам не кажется, что ваше решение масштабируется немножко нелинейно?

apelserg 16 авг 2015 в 09:59

вам не кажется, что ваше решение масштабируется немножко нелинейно?

За стремление к линейности или там, «горизонтальности» придётся платить так-же как за стремление к реалтайму (в ИТ чудес не бывает — это не магический чёрный ящик).

lair 16 авг 2015 в 10:13

… что снова говорит нам, что объем данных влияет на трудоемкость. Иначе чем вы «платите»?

apelserg 16 авг 2015 в 12:42

По трудоёмкости смотите ветку выше.

[Close]

Mrrl 16 авг 2015 в 20:06

Чтобы это сделать на CSV-файле, вам придется читать все записи до нужной вам (структура файла не позволит вам быстро и дешево пропустить ненужное).
Мы вполне можем за первый проход составить карту файла — с какого места начинается первая запись, с какого N+1-я, и т.д. Тогда читать очередной миллиард будет легко.
Кстати, можно этого и не делать. Оба файла читаются последовательно (один — 1 раз, другой — 10 раз). Можно их после очередной порции просто не закрывать.
Другое дело, что если записи идут не подряд, то для заполнения очередного миллиарда id нам придётся просматривать весь файл. Но, поскольку файл связей мы всё равно читаем целиком, это повлияет только на коэффициент, сложность будет O(N*K^3).

lair 16 авг 2015 в 20:11

Мы вполне можем за первый проход составить карту файла — с какого места начинается первая запись, с какого N+1-я, и т.д. Тогда читать очередной миллиард будет легко.

Конечно, можем. Только это усложняет алгоритм. Речь-то о том, что в тот момент, когда данные перестают (с запасом) влезать в память, алгоритм начинает усложняться (если, конечно, он изначально не был написан из расчета на константное потребление). Сложнее алгоритм — выше трудоемкость. Q.E.D.

lair 15 авг 2015 в 20:16

Я имею в виду, что ваше решение хорошо работает до тех пор, пока идентификаторы числовые.

Кстати, даже когда идентификаторы числовые, они при этом могут быть непоследовательными. Что тоже рушит картинку с массивами.

apelserg 15 авг 2015 в 21:24

Увы, здесь всё работает корректно. От последовательности данных ничего не зависит. Если вы так увлеклись, то можете сгенерировать тестовые данные на 1000 записей и убедится в этом.

lair 15 авг 2015 в 21:55

Представьте, что у вас записей тысяча, но их идентификаторы идут не 0, 1, 2, 3..., а 1, 4, 10 и так далее. Всегда возрастают, но не подряд.

(это, что характерно, совершенно жизненная ситуация).

apelserg 16 авг 2015 в 10:04

И опять, увы… Идентификаторы могут иметь любую последовательность и любые пропуски, главное, чтобы размер массива был не меньше максимального числового значения идентификатора. В этом одновременно и сила и слабость индесного массива — не для всех задачь он применим, но если задача соответствует — скорость поиска будет стремиться к теоритически возможной.

Кстати, если данных не так много (несколько миллионов), то их лучше обрабатывать в СУРБД.

lair 16 авг 2015 в 10:14

Идентификаторы могут иметь любую последовательность и любые пропуски, главное, чтобы размер массива был не меньше максимального числового значения идентификатора.

Я об этом и говорю. Для того, чтобы ваше решение поддержало «любые пропуски», вам, во-первых, придется выделять больше памяти, а во-вторых, каким-то образом заранее определять это самое «максимальное значение».

apelserg 16 авг 2015 в 12:44

В примере так и сделано, посмотрите код.

[Close]

lair 16 авг 2015 в 12:51

Нет, в примере сдеано вот так:

int totalMax = 1000000000;
antList = new byte[totalMax + 1];
cellList = new byte[totalMax + 1];
/*...*/
int idx = int.Parse(strList[0]);
antList[idx] = byte.Parse(strList[1]);
/*...*/
int idx = int.Parse(strList[0]);
cellList[idx] = byte.Parse(strList[1]);

У вас нет вычисления максимального значения.

apelserg 17 авг 2015 в 12:56

Приношу извинение, что задержался с ответом.

Максимальное значение известно заранее — миллиард.

«Цель публикации — поделиться опытом как, за приемлемое время, обработать два связанных списка по миллиарду записей в каждом.»

lair 17 авг 2015 в 13:27

Это не максимальное значение, это максимальное количество. Представьте себе, что у вас есть миллиард записей, идентификатор первой из которых начинается с 999999.

(вы серьезно никогда не видели дыр в ключевых диапазонах?)

apelserg 17 авг 2015 в 13:59

В демо-примере максимальное значение равно максимальному количеству и соответствует количеству тестовых данных. Тестовые данные подготовлены без пробелов.

Реальные данные допускают существование пробелов.
Реальный размер массива должен быть не меньше максимального значения. Максимальное значение (результат инкрементальной функции) не вычисляется, а смотрится в БД и устанавливается с запасом. Запас согласовывается с требованиями Заказчика и определяется исходя из среднего количества прироста на единицу времени.

Если все эти типовые, для такого типа задач, условия были непонятны из содержания публикации и вызывали затруднения и вопросы, то приношу свои извинения.

lair 17 авг 2015 в 15:12

Максимальное значение (результат инкрементальной функции) не вычисляется, а смотрится в БД и устанавливается с запасом

Ну, вы же понимаете, что у вас тогда расход памяти еще веселее становится?

И нет, это не типовые условия, потому что, например, у меня в типовых проектах целочисленных идентификаторов не было лет пять-восемь.

apelserg 17 авг 2015 в 15:46

Ну, вы же понимаете, что у вас тогда расход памяти еще веселее становится?

Да, я понимаю. Мне повезло, условия проекта были такие. В память всё влезло и никто не парился. Уверен, что существенный процент задач могут быть решены подобным образом.

И нет, это не типовые условия, потому что, например, у меня в типовых проектах целочисленных идентификаторов не было лет пять-восемь.

Это странно, делают конечно распредлённые системы на GUID-ах, но делают и по-другому, например на составных целочисленных ключах, или выделяют диапазоны. Так, что я утверждаю — вполне типовые.

lair 17 авг 2015 в 15:48

В память всё влезло и никто не парился.

Ну, при таком подходе объем данных действительно не влияет на трудоемкость.

apelserg 17 авг 2015 в 18:47

А разве вы закладываете в проекты только универсальные решения? Каждый проект имеет свои ресурсные ограничения. Поэтому лёгкие функциональные решения не редко ценятся выше трудоёмких универсальных. Тем более лишняя трудоёмкость вовсе не гарантирует лучшего качества.

lair 17 авг 2015 в 19:05

А разве вы закладываете в проекты только универсальные решения?

Конечно, нет. Я закладываю в проекты решения, которые работают в заданных границах нагрузки, и исходя из этих границ расчитываю трудоемкость.

apelserg 17 авг 2015 в 19:48

А как вы поступаете, если, например, расчитанная трудоёмкость полгода, а найденное решение уложилось в 2 недели и нашли это решение «в соседнем отделе»? Или такого быть не может?

lair 17 авг 2015 в 19:56

Записываем в книжечку как удачную ошибку, в следующий раз учтем.

apelserg 17 авг 2015 в 20:12

Вы легко списываете полгода потраченного времени, но несколько гигабайт памяти, которые экономят эти полгода, считаете «дорогими». Где здесь логика? Вы можете объяснить?

lair 17 авг 2015 в 20:15

Так почему же «потраченное»-то время? Мы выставили клиенту контракт на полгода, он согласился, мы получим за это деньги. То, что мы внутри себя нашли решение — это наш конкурентный недочет, мы его в следующий раз учтем, и выставим меньшие сроки, чтобы быть выгоднее для клиента.

Другое дело, что в среднем проект состоит не из одной задачи, на одной ошибаются в минус, на другой — в плюс, и в итоге, если повезет, проект сойдется в срок. Чаще всего не сходится, потому что ошибок в минус на порядок меньше, чем в плюс.

apelserg 17 авг 2015 в 20:32

Обычно бывает именно так, как вы описываете. Но, довольно часто, именно в настоящее время, Заказчик контракт подписывает, но остаётся недовольным и продолжает поиск исполнителя. Вас при этом, он в известность не ставит. И, если поиск удаётся, все недоработки по проекту — это основания, чтобы контракт разорвать, а если выясняется (не без помощи нового исполнителя), что была завышена смета, то легко получить претензию по неустойке.

А надо-то было всего докупить два чипа памяти.

lair 17 авг 2015 в 20:50

Там вот выше написано — решения, которые работают в заданных границах нагрузки. В заданные границы, вы не поверите, память тоже входит. Соответственно, если можно «докупить два чипа памяти» (вы еще попробуйте это сделать для сервера, находящегося на чужом гарантийном обслуживании), то это в задаче учтено. Чаще всего — нельзя.

apelserg 18 авг 2015 в 09:12

Выходит, что вы вовсе не против добавления памяти. Тогда поясните в чём должен состоять «сухой остаток» нашего обсуждения?

lair 18 авг 2015 в 09:13

В том, что добавление памяти не всегда возможно. И если вам дана задача, которая в память (включая возможное добавление) не лезет, вам придется подпрыгивать, чтобы ее решить.

apelserg 18 авг 2015 в 09:36

Разочарование. Такое бурное обсуждение ради такого банального вывода.

Mrrl 18 авг 2015 в 09:39

Вот только этот «банальный вывод» противоречит тезису из «краткого резюме» — что «что объём данных не оказывает существенного влияния на трудоёмкость разработки»…

apelserg 18 авг 2015 в 10:27

Вот только этот «банальный вывод» противоречит тезису из «краткого резюме»

Как раз никакого противоречия нет. Планируйте трудоёмкость «правильно» и живите спокойно.
«Правильно» в данном случае — хорошее знание матчасти и умение её применять в деле.
Ну и, конечно, без простого везения не обойтись (у английских капитанов, в личном деле, даже была такая графа — везучесть).

Mrrl 17 авг 2015 в 20:01

Ну, это просто. Разбираемся в этом решении, после чего объясняем авторам и начальству, почему оно не будет работать.

apelserg 17 авг 2015 в 20:21

А к вам не могут зайти простые ребята с трёхдневной небритостью? «Ночной кошмар программиста». Мне известны примеры, когда так были потеряны большие проекты.

Mrrl 18 авг 2015 в 09:19

Буду только счастлив — можно будет переключиться на другие части проекта, которые ждут своей очереди, а заодно и научиться чему-нибудь новому. Вот только пока попытки воспользоваться математикой со стороны к успеху не приводят: например, недавно какие-то шотландцы предложили включить их код в наш проект (чтобы пользователи могли пользоваться их фотокамерой). Пока что не удаётся заставить работать их же тестовый пример (для их SDK). По тем частям, которые уже работают, видно, что скорость, мягко говоря, не очень… Но мне сейчас слегка некогда писать альтернативный алгоритм, хотя все основные идеи уже видны.

rogalskiy 18 авг 2015 в 15:26

Я бы решил задачу с помощью облачного решения основанного на теории конечных автоматов. Если говорить про трудоемкость разработки, то это заняло бы полчаса и подходило под любые нагрузки, которые способны выдержать сервера Amazon. Вопрос в подходе

Зарегистрируйтесь на Хабре, чтобы оставить комментарий