Сообщение Re[2]: Как правильно сортировать содержимое больших файлов? от 21.08.2022 12:37
Изменено 21.08.2022 12:56 _FRED_
Re[2]: Как правильно сортировать содержимое больших файлов?
Здравствуйте, Буравчик, Вы писали:
_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
Б>Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Б>Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.
Б>А должно работать за O(N * log K)
Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?
Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
Б>Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Б>Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.
Б>А должно работать за O(N * log K)
Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?
Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
Re[2]: Как правильно сортировать содержимое больших файлов?
Здравствуйте, Буравчик, Вы писали:
_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
Б>Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Б>Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.
Б>А должно работать за O(N * log K)
Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?
Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.
_FR>>Вот с тех пор мне интересно, где я мог пойти не тем путём: разница достаточно большаая, скорее всего на более медленном железе так плохо вышло не из-за каких-то микрооптимизаций, которые я не смог сделать, а в чём-то принципиальном. Но где
Б>Считаю, проблема в том, что у тебя MergeFilesAsync работает за O(N*K), где N — общее количество строк в исходном файле, и K — количество чанков.
Б>Потому что на каждую строку ты меняешь список items с помощью операций Insert/RemoveAt.
Б>А должно работать за O(N * log K)
Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?
Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
P.S. Если вообще "отключить" сортировку, то есть удалять последний элемент списка и новую строку всегда добавляить в конец же, то 1,976 файлов сливаются за 8..9 секунд. Всё-таки кажется, что проблема не в этом.