Как бы вы делали эту задачу (переходим к конкретике)... - О работе

Здравствуйте, Gt_, Вы писали:

Gt_>ну нафлеймили. очевидно же что это задание на знание map-reduce парадигмы и про параллельность. совершенно типичная задача на позиции Data Engineering. правда обычно все же устно просят рассказать и бывает ждут что расскажут про многоблочное чтение (readFileScattered из winapi).

А чем эта функция отличается от обычного ReadFile в асинхронном режиме?

Gt_>>ну нафлеймили. очевидно же что это задание на знание map-reduce парадигмы и про параллельность. совершенно типичная задача на позиции Data Engineering. правда обычно все же устно просят рассказать и бывает ждут что расскажут про многоблочное чтение (readFileScattered из winapi).

M>А чем эта функция отличается от обычного ReadFile в асинхронном режиме?

не дергает процессор и читает мимо виндового кеша сразу несколько блоков с устройства через DMA, мимо процесора. обычный read читает из кеша винды по одном блоку, дергает cpu ...

Здравствуйте, Shmj, Вы писали:

S>Т.е. вы сразу готовы бодаться с заказчиком и в судах отстаивать что было выполнено все по Т.З.?
Не без этого, да...

S>А если заказчик сам не до конца понимает как сделать лучше? И хочет чтобы вы были его другом, подсказали оптимальный вариант.
Вот, я рад, что ты сам подошел к этому. Да, заказчик сам не до конца понимает, что же он хочет получить. Именно так. И именно по этому на сбор и анализ требований уход много сил и времени. Я уже писал когда-то, что на одном проекте пока я составлял расширенное ТЗ требования менялись раз пять, причем на диаметрально противоположные. И это в общем-то нормально. Процесс работы с требованиями итерационный, это постоянные интервью, наблюдения, иногда даже участие в процессе, местами иногда телепатия

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

).

Здравствуйте, AmSpb, Вы писали:

AS>Сотрудники Kaspersky сообщили о предложении уволиться на просьбы о переезде из России

Угу. Ученый изнасиловал журналиста.

Правда заключается в том, что ЛК не может обеспечить возможность удаленной работы для сотрудников, уехавших из России. Тех, кто хочет/планирует уехать, но еще не уехал, никто никак не обижает.

Здравствуйте, Shmj, Вы писали:

S>В продолжение темы: https://rsdn.org/forum/job/8342543.flat
S>Многие думают, что главное собрать требования а остальное легко — что требования собрать — это большая часть времени а разработка типа 15%.

S>Ну ок, чтобы далеко не ходить, давайте популярную задачу, которую уже дважды на днях поднимали:

S>1. https://rsdn.org/forum/dotnet/8335182.flat
S>2. https://rsdn.org/forum/alg/8340088.flat

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

S>Вот мое видение на скорую руку: https://rsdn.org/forum/dotnet/8338266.1

S>Идея такая, что для такой задачи не оптимально писать все с нуля а правильнее найти готовое решение.

S>Но! Прав ли я? Во-первых, мое решение не доделано — там сортируется сначала по цифре, потом по строке (но это ладно, можно поменять местами). Второе — не учитываются дубликаты (можно прибавить к каждой записи счетчик или задействовать Berkeley DB, вроде там дубликаты разрешены, но это не точно).

S>Как бы вы это решали? Искали бы сначала готовую библиотеку или же писали бы с нуля?

S>Ну и как думаете — если мое решение с LevelDB довести до ума — будет ли быстрее чем предложенные самописные решения на сотнях гигабайт данных? Ведь больше 2-3 Гб. никто проверять не хочет, а это размер, который полностью вмещается в ОЗУ. Когда в ОЗУ перестанет влазить — цифры могут быть другими.

S>Вот я реально не знаю. Нужно только проверять. А проверить с 50 Гб. данных — уже час времени.

Ну вот допустим, ты приходишь к оптинскому старцу, человеку с большим жизненным опытом решения жизненных же проблем (тынц: https://rsdn.org/forum/life/8347891, или тынц: https://rsdn.org/forum/flame/8346842, или даже https://rsdn.org/forum/life/8347606). Ты описываешь ему проблему, а про себя думаешь, ну что какой-то там старец может тут сделать, он же ни на одну кнопку в жизни не нажимал, и ни про какие О-большое не слыхивал даже, ты описываешь ему свою проблему, он тебя спрашивает — а ты, мил человек, решением энтой своей зандачей многим людям мирским поможешь в жизни их? И ты такой — опа, а что ответить-то мудрому человеку? И вопрос-то он задал дурацкий, не по делу, не решает он твою зандачу, и пойдешь ты от него, и станешь всем говорить, что старцы на то только и годятся, что место им уступать в трансопрте.

Здравствуйте, Shmj, Вы писали:

S>Сколько по времени отработает эта утилита на 100 Гб данных?

Лениво проверять. Если интересно — сравни с другими реализациями.

Здравствуйте, AleksandrN, Вы писали:

AN>Лениво проверять. Если интересно — сравни с другими реализациями.

Не то лениво — это просто затраты времени и ресурсов.

Здравствуйте, Gt_, Вы писали:

Gt_>Я бы для начала попробовал spark, он даже локально распараллелит чтение

протестил spark+java на 12700k и стареньком sata ssd, 10G файлик.

@SpringBootTest
@TestInstance(TestInstance.Lifecycle.PER_CLASS)
class BigFile {

    @Test
    void bigfile0() throws IOException {
        SparkSession spark = SparkSession
                .builder()
                .appName("delta")
                .master("local[*]")
                .getOrCreate();

        spark.read()
                .option("delimiter", ".")
                .csv("D:/TEST")
                .sort("_c1", "_c0")
                .repartition(1)
                .write()
                .option("delimiter", ".")
                .csv("D:/TEST_COMBINED");


    }

тест прошел 2m14s, убрал repartition(1), попробовал руками конкатинировать 200 файлов что спарк по дефолту выплевывает — вышло дольше 2m31s

на HDD с repartition(1) 9 минут писал.

Здравствуйте, Shmj, Вы писали:

S>Многие думают, что главное собрать требования а остальное легко — что требования собрать — это большая часть времени а разработка типа 15%.
Это запомним

S>Требования собраны, всем все понятно. Только абсурдировать не нужно, понятно что демагогическими приемами все можно свести к абсурду, любая фраза не формальна и не полна. По сути всем все понятно.
S>Вот мое видение на скорую руку: https://rsdn.org/forum/dotnet/8338266.1
S>Идея такая, что для такой задачи не оптимально писать все с нуля а правильнее найти готовое решение.
S>Но! Прав ли я? Во-первых, мое решение не доделано — там сортируется сначала по цифре, потом по строке (но это ладно, можно поменять местами). Второе — не учитываются дубликаты (можно прибавить к каждой записи счетчик или задействовать Berkeley DB, вроде там дубликаты разрешены, но это не точно).
Конечно ты не прав.
Во-первых твое решение, как ты сам заметил, не доделано. Доделка не представляется тривиальной.
Во-вторых требование сортировать сначала по строке, а потом по числу — ключевое. Если немного проанализировать это требование, то становится понятно, что мы никаким образом не сможем построить эффективный индекс.
Так как ключом является строка, то её надо хранить в индексе полностью, это означает что индекс точно не влезет в память. Внешний индекс потребует O(N * log N) операций записи на диск, тогда как разбиение файла на куски, сортировка кусков в памяти и слияние кусков потребует ровно 2*N записей на диск.
В-третьих ты не думая применил async, хотя для такой задачи он не помогает. Я думаю большинство C# программистов сделает также, я тоже так сделал. Но оказалось что async в такой задаче не помогает. Это тоже могло быть уточнено при анализе, но мы же программисты, нам "написать быстрее, чем описать".
В-четвертых, то что пропустили почти все, в условиях мало что известно о природе строк. Многие посчитали их ASCII-строками (массивами байт-символов), тогда как может быть UTF-8 с правилами сортировки для Норвежского языка.

S>Как бы вы это решали? Искали бы сначала готовую библиотеку или же писали бы с нуля?
Я немного проанализировал и понял что можно почти все написать с помощью стандартных пакетов.
Вот решение https://github.com/gandjustas/HugeFileSort
Я примерно полчаса поискал библиотеки для megre двух IEnumerable и для min heap и не нащел ничго внятного. Merge написал сам, а вместо min heap использовал стандартный PriorityQueue

S>Ну и как думаете — если мое решение с LevelDB довести до ума — будет ли быстрее чем предложенные самописные решения на сотнях гигабайт данных?
Не будет

S>Ведь больше 2-3 Гб. никто проверять не хочет, а это размер, который полностью вмещается в ОЗУ. Когда в ОЗУ перестанет влазить — цифры могут быть другими.
14 ГБ файл (100 000 000 строк), генерация заняла 160 сек
Сортировка — 360 сек
На HDD все проверялось.

К сожалению все еще влезает а ОП на моей машине, но во время работы больше 3гб не съел.

S>Вот я реально не знаю. Нужно только проверять. А проверить с 50 Гб. данных — уже час времени.
LevelDB в час не уложится, только если SSD очень быстрый.

Здравствуйте, Shmj, Вы писали:

S>Речь была о том, что сбор и анализ требований — это основная часть работы. Причем тут продажи и документация?

Кажется, речь была о том, что программирование — это 15% от всей разработки, которая включает анализ и все такое.
И эти остальные активности никуда не денутся.
Конкретно ты можешь их посылать в сад и игнорировать эти активности. Значит, этим будут заниматься другие люди. Или не будут. Но тогда придет пушной зверек, и не один.
То есть конкретно ты можешь тратить на программирование 50% и даже больше.
Но в разработке вообще оно займет порядка 15%. Где-то больше, где-то меньше.

Здравствуйте, Gt_, Вы писали:

Gt_>тест прошел 2m14s, убрал repartition(1), попробовал руками конкатинировать 200 файлов что спарк по дефолту выплевывает — вышло дольше 2m31s

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

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

Сложно ли вам кастомизировать сортировку?

Здравствуйте, gandjustas, Вы писали:

G>Я немного проанализировал и понял что можно почти все написать с помощью стандартных пакетов.
G>Вот решение https://github.com/gandjustas/HugeFileSort
G>Я примерно полчаса поискал библиотеки для megre двух IEnumerable и для min heap и не нащел ничго внятного. Merge написал сам, а вместо min heap использовал стандартный PriorityQueue

И сможешь ли сказать честно — сколько времени ушло на все, включая анализ и пр.?

Данные вашего решения на машине Google Cloud (4 ядра, 16 Гб ОЗУ) с SSD:

100 млн. записей, 13,8 Гб:

Генерация — 437 сек. (7,2 мин.)
1 Гб — 32 сек.

Сортировка — 934 сек (15,5 мин.)
1 Гб — 68 сек.

Gt_>>тест прошел 2m14s, убрал repartition(1), попробовал руками конкатинировать 200 файлов что спарк по дефолту выплевывает — вышло дольше 2m31s

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

да, бинарная. причем sort() это я не подумав использовал (sort внутри партиции сортирует, а не весь датасет), там orderBy() вместо него должен быть и цифровую часть следовало кастить в инт, иначе как строку сортирует.
подправил — 15 секунд прибавилось.

S>

S>В-четвертых, то что пропустили почти все, в условиях мало что известно о природе строк. Многие посчитали их ASCII-строками (массивами байт-символов), тогда как может быть UTF-8 с правилами сортировки для Норвежского языка.

S>Сложно ли вам кастомизировать сортировку?

да, сложно. свой компаратор можно подсунуть в sort() партиции, но сортировать внутри партиции нет смысла, т.к. весь файл в одну партицию по памяти не влезет.

Здравствуйте, Gt_, Вы писали:

Gt_>да, бинарная. причем sort() это я не подумав использовал (sort внутри партиции сортирует, а не весь датасет), там orderBy() вместо него должен быть и цифровую часть следовало кастить в инт, иначе как строку сортирует.
Gt_>подправил — 15 секунд прибавилось.

Gt_>да, сложно. свой компаратор можно подсунуть в sort() партиции, но сортировать внутри партиции нет смысла, т.к. весь файл в одну партицию по памяти не влезет.

repartition(1) — это на сколько частей разбить файл?

Оно точно не в памяти файл целиком хранит?

Здравствуйте, gandjustas, Вы писали:

G>Вот решение https://github.com/gandjustas/HugeFileSort

Сортировка в 2.5 раза медленнее у вас, чем этот вариант: https://rsdn.org/forum/alg/8351025.1

Задание одно и тоже. Требования всем понятны. А вот как решить оптимально — вот это хрен знает. Нужна компетенция колоссальная.

Здравствуйте, Shmj, Вы писали:

https://itamargilad.com/gist-framework/

Gt_>>да, сложно. свой компаратор можно подсунуть в sort() партиции, но сортировать внутри партиции нет смысла, т.к. весь файл в одну партицию по памяти не влезет.

S>repartition(1) — это на сколько частей разбить файл?

S>Оно точно не в памяти файл целиком хранит?

процесс жрет 5-6 гигов, пока не понял почему, я вроде driver двумя гигами ограничивал. repartition(1) завязан на write(), думаю он получает стрим и на ходу записывает в файл. можно убрать repartition(1), но тогда придется самому склеивать 200 файлов от партиций что оставит orderBy().
я думаю оно работает так — файл разбивается на 200 частей — маперы читают, отправляют на 200 редюсоров, те устраивают сортировку внутри партиции — во на выходе и 200 RDD с отсортированным датасетом. на сколько помню RDD может сбрасываться на диск, если памяти не хватает.

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, gandjustas, Вы писали:

G>>Я немного проанализировал и понял что можно почти все написать с помощью стандартных пакетов.
G>>Вот решение https://github.com/gandjustas/HugeFileSort
G>>Я примерно полчаса поискал библиотеки для megre двух IEnumerable и для min heap и не нащел ничго внятного. Merge написал сам, а вместо min heap использовал стандартный PriorityQueue

S>И сможешь ли сказать честно — сколько времени ушло на все, включая анализ и пр.?
Часа два смотрел видос и читал что люди написали.
Полчаса первый прототип — похоже на итоговое решение
Потом часа три пытался "оптимизировать" не шибко удачно
Потом еще час доводил прототип до текущего состояния

Здравствуйте, Shmj, Вы писали:

S>Здравствуйте, gandjustas, Вы писали:

G>>Вот решение https://github.com/gandjustas/HugeFileSort

S>Сортировка в 2.5 раза медленнее у вас, чем этот вариант: https://rsdn.org/forum/alg/8351025.1

Сделано в предположение, что файлы ASCII

Это слишком сильное предположение как по мне. Хотя как раз на строки (преобразование и уборка мусора) тратится почти половина не-IO времени.
Если рассматривать строки как ascii, то можно zero-allication код сделать, который будет до 10 раз быстрее там где не-IO. Но все равно хороший ССД даст прирост по скорости больше чем микрооптимизации.

S>Задание одно и тоже.
По факту нет. Разница unicode и ascii строк огромная.

S>Требования всем понятны.
Требования для этой задачи не полны, увы. В том числе требования быстродействия.

S>А вот как решить оптимально — вот это хрен знает. Нужна компетенция колоссальная.
Какой параметр мы оптимизируем?
Если время работы программы, то можно взять наивную реализацию на питоне или .net и поставить диски побыстрее.
Если суммарные затраты в денежном эквиваленте, то непонятно как оценивать разницу во времени работы даже в два раза.
Если процессорное время или затраты памяти, то надо переписывать на С\C++\Rust и отказаться от управляемых сред.

Вообще само определение критерия оптимальности может занять те самые 85% времени.

Здравствуйте, gandjustas, Вы писали:

S>>И сможешь ли сказать честно — сколько времени ушло на все, включая анализ и пр.?
G>Часа два смотрел видос и читал что люди написали.
G>Полчаса первый прототип — похоже на итоговое решение
G>Потом часа три пытался "оптимизировать" не шибко удачно
G>Потом еще час доводил прототип до текущего состояния

Т.е. уже ушло 2+1.5+3+1=7.5 часов — минимум рабочий день вы потратили.

Причем будем откровенны — вы один из лучших спецов по .Net в нашем сообществе, во всяком случае в плане знания платформы/библиотек и практических решений.

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	30.08.22 13:52
Оценка:

	От:	Gt_
	Дата:	30.08.22 14:02
	Оценка:

	От:	Dym On
	Дата:	30.08.22 14:10
	Оценка:

От:	Pzz	https://github.com/alexpevzner
Дата:	30.08.22 19:54
Оценка:

	От:	gyraboo
	Дата:	30.08.22 20:05
	Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	02.09.22 10:00
Оценка:	11 (2)

	От:	Shmj
	Дата:	31.08.22 10:06
	Оценка:

	От:	Shmj
	Дата:	04.09.22 05:36
	Оценка:

	От:	Shmj
	Дата:	04.09.22 09:42
	Оценка:

	От:	Shmj
	Дата:	04.09.22 12:08
	Оценка: