Недавно мы с коллегой обсуждали, влияет ли объем данных на сложность разработки.
Сухой остаток остается:
- Объем данных не должен оказывать существенного влияния на сложность разработки.
Основная сложность разработки, как правило, связана со сложностью алгоритма обработки данных, а не с их количеством.
Зная заранее реальный объем данных, достаточно разработать код, работающий с небольшими данными, а затем его можно будет применить к необходимому объему.
- Все основные вычислительные алгоритмы известны давно (по крайней мере, несколько десятилетий).
Главное – как можно раньше (до начала разработки) определить правильный подход к проблеме.
Но это вопрос не трудоемкости, а профессиональной пригодности - то есть аппаратное обеспечение должно быть заранее изучено и быстро разработано.
- Ни один Заказчик не поймет, почему сложность разработки кода в несколько сотен строк отняла много времени.
Заказчику проще сменить команду, чем вкладывать свое время и деньги в чей-то процесс обучения или в какой-то непонятный ему эксперимент.
- Конечно, могут быть некоторые небольшие накладные расходы, связанные с объемом данных.
Но эти затраты обычно не превышают погрешности первоначальной (правильной) оценки трудоемкости и учитывать их отдельно не имеет смысла.
Но дискуссия возникла не на пустом месте, а в рамках обсуждения задачи с простым вычислительным алгоритмом, но большим объемом данных.
Цель публикации — поделиться опытом обработки двух связанных списков по миллиарду записей в каждом за приемлемое время.
Постановка задачи
Данные, представленные в публикации, аналогичны данным исходной задачи.Изменения коснулись преимущественно прикладной терминологии.
Назовем это «Бухгалтерия в муравейнике».
Чтобы проиллюстрировать процесс, он выглядел так: В одном сказочном лесу решили провести перепись животных.
Для этого они создали простую систему учета, куда записывали всех животных – всего около тысячи.
Была создана система, животным были присвоены номера, а также норкам, берлогам и гнездам.
Короче говоря, все оказалось просто и быстро.
Об этом они узнали в муравейнике и тоже решили разработать свою систему учета.
За основу взята система регистрации животных.
В результате каждый муравей получил номер имени и номер дома.
Каждому муравью был присвоен тип: рабочий, солдат,.
Дома были распределены по площадям муравейника: центр, верх, низ,.
После завершения учета и на муравьином собрании все радостно отметили завершение работы, слово взял главный муравей-солдат. Он сказал (разумеется, говорил, раздавая всякие феромоны - муравьям понятнее), что бухгалтерия ему нравится, это нужная и полезная вещь, и теперь надо рассылать списки муравьев-солдат, живущих в этой части.
муравейника во все части муравейника.
Сделать это необходимо, как обычно принято в таких случаях, срочно и без промедления.
Тут начали суетиться и другие представители муравьев — им тоже нужны были списки для распространения всяких червячных жучков и для проведения других не менее важных мероприятий.
И муравьев было миллиард. 
Структура данных представлена на рисунке:
- ant_type - виды муравьев (1 - королева, 2 - личинка, 3 - няня, 4 - рабочий, 5 - солдат)
- Hill_type - районы муравейника (1 - центр, 2 - верх, 3 - низ, 4 - север, 5 - юг, 6 - восток, 7 - запад)
- ant_list — список муравьев (миллиарды записей)
- cell_list — список домов (млрд записей)
- ant_to_cell — какой муравей в каком доме живет (миллиард записей)
Данные испытаний
Для интересующихся есть утилита для генерации тестовых данных.Утилита подготовлена в виде консольной программы, написанной на C# (Visual Studio Community 2013).
Код утилиты выложен на GitHub в файле муравейник-makedata.cs .
Чтобы получить работающую программу в Visual Studio, необходимо создать консольный проект, заменить файл program.cs на anthill-makedata.cs и собрать проект. Такой подход был выбран с точки зрения компактности, наглядности и безопасности распространения.
По умолчанию (без параметров) утилита готовит набор тестовых данных (5 файлов в формате CSV) на тысячу записей.
В качестве параметра можно указать желаемый размер данных — от тысячи до миллиарда: anthill-makedata.exe 1000000000 Подготовка тестовых данных из миллиарда записей займет до 30 минут и около 50 Гигабайт дискового пространства.
Время выполнения можно посмотреть в журнале (anthill-makedata.log).
Вы можете использовать FAR для просмотра данных.
Решение
Здесь для интересующихся можно подумать, как бы они решили эту проблему.В процессе разработки выяснилось, что моё железо «не очень хорошее», поскольку ни при первом, ни при втором прогоне не удалось добиться приемлемой производительности.
Обработка полных данных была очень и очень медленной.
Причиной тому стала процедура поиска, которая выполнялась быстро на небольших данных, но по мере увеличения данных все неприлично замедлялось.
В конце концов решение было найдено.
Более того, даже того, что было под капотом моего не очень мощного компьютера, хватило для работы с полными данными: CPU — Core 5i, RAM — 12Gb (было 8, добавилось 4), HDD — самый простой (5400 об/мин).
Суть решения — использовать обычный индексный массив.
Для каждого списка создается массив размером в миллиарды.
Номер ячейки массива соответствует номеру объекта (муравей, дом).
В ячейках массивов размещаются идентификаторы типов муравьев и типов частей муравейников соответственно.
После заполнения массивов муравьев и домиков (из тестовых данных — файлов anthill-ant-list.csv и anthill-cell-list.csv) «растягивается» файл подключения anthill-ant-to-cell.csv. и файлы (CSV) с результатами.
Доступ к ячейке массива по индексу происходит мгновенно, так как не тратится время на поиск.
При этом основная часть времени тратится на чтение и запись файлов (работа с HDD).
Решение подготовлено в виде консольной программы, написанной на C# (Visual Studio Community 2013).
Код программы выложен на GitHub в файле anthill-makeresult.cs .
Чтобы получить работающую программу в Visual Studio, необходимо создать консольный проект, заменить файл program.cs на anthill-makeresult.cs и собрать проект (обратите внимание: в свойствах проекта в разделе BUILD снимите флажок [Предпочитать 32 -кусочек]).
Программу следует запускать в той же директории, где находятся файлы тестовых данных.
По умолчанию (без параметров) программа готовит списки муравьев-солдат (CSV-файлы).
Вы можете указать желаемый тип в качестве параметра: anthill-makeresult.exe 4 (4 — код «рабочего» типа) Подготовка результатов на основе полных данных занимает до 30 минут. С учетом тестовых данных потребуется около 100 Гигабайт дискового пространства.
Краткое содержание
Для рассматриваемой задачи оказалось верным утверждение о том, что объем данных не оказывает существенного влияния на сложность разработки:- Готовое решение оказалось простым и уместилось в 300 строк кода, включая обработку ошибок, логирование и комментарии.
- Решение одинаково работает как с небольшими, так и с большими (до заданного размера) данными.
- Основной тормоз не в обработке данных, а в операциях ввода/вывода (медленная работа HDD).
- Подход не является универсальным.
Например, на решение может оказать существенное влияние другая структура или другой формат данных приложения.
- Работа с CSV-файлами не всегда удобна, не защищена от ошибок и не гарантирует целостности данных.
-
Ежеквартальный Отчет Apple
19 Oct, 24 -
Вышла Вторая Альфа-Версия Ubuntu 9.04
19 Oct, 24 -
Gamma Gallery — Отличная Адаптивная Галерея.
19 Oct, 24
