ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
25 сообщений из 55, страница 1 из 3
  1  все
Сортировка сотен миллионов строк с удалением дублей
    #39833061
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
А что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).
...
Рейтинг: 0 / 0
03.07.2019, 02:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833077
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
registeredА что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).
В Вашем случае прямо таки напрашивается использование какой нибудь СУБД. Возможно встроенной, например SQLite или Firebird embedded.

Загоняете массив строк в табличку, а далее уже SQL выражениями делаете любую выборку. Все современные СУБД делают это очень быстро.
...
Рейтинг: 0 / 0
03.07.2019, 06:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833115
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

СУБД?
Ради сортировки строк?
Реально?
...
Рейтинг: 0 / 0
03.07.2019, 10:12
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833127
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registered,

Быстрей можно всегда, только это ручками делать надо.
Например побить свой лист на много более мелких. Так сортировка будет работать значительно быстрей.
...
Рейтинг: 0 / 0
03.07.2019, 10:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833140
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
registeredА что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).1. фиговые дела происходят, блочное копирование
2. незначительно

метод сортировки в узких случаях нужно подбирать индивидуально, реализация сортировки в TSringList от дельфи, редкий позор
+ сортировка Хаора очень чувствительна к функции сравнения
...
Рейтинг: 0 / 0
03.07.2019, 11:10
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833153
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
var
  Basis: TArray<string>;
begin
  Randomize;
  SetLength(Basis, 10000000);
  for var k := Low(Basis) to High(Basis) do
    Basis[k] := Random(k).ToString();
 TArray.Sort<string>(Basis);


+ можно через TTask распараллелить по кускам и потом склеить, будет быстрее в зависимости от кол-ва ядер и процессоров.
...
Рейтинг: 0 / 0
03.07.2019, 11:30
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833176
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Я тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

разбиение на 4 равные части
сортировка каждой части на отдельном ядре
слияние 4 частей в 1 массив

заняло 5 секунд
...
Рейтинг: 0 / 0
03.07.2019, 11:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833181
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
X-Cite,

вся беда таких тестов что они не учитывают реальные данные и особенности алгоритмов
...
Рейтинг: 0 / 0
03.07.2019, 12:03
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833184
Tactical Nuclear Penguin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Tactical Nuclear Penguin
Участник
X-CiteЯ тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

разбиение на 4 равные части
сортировка каждой части на отдельном ядре
слияние 4 частей в 1 массив

заняло 5 секунд

ты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...
...
Рейтинг: 0 / 0
03.07.2019, 12:05
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833208
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

СУБД?
Ради сортировки строк?
Реально?

Сортировка с выкидыванием дублей. TStringList так вроде не умеет.

А в чем собственно проблема ?
...
Рейтинг: 0 / 0
03.07.2019, 12:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833210
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
А можно еще хешик сделать. На первые несколько букв строки.
И сортировать по хэшу.
...
Рейтинг: 0 / 0
03.07.2019, 12:42
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833212
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

То есть вы не видите проблемы?
...
Рейтинг: 0 / 0
03.07.2019, 12:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833217
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
black-manateeСортировка с выкидыванием дублей. TStringList так вроде не умеет.
Да ну правда что ли?
...
Рейтинг: 0 / 0
03.07.2019, 12:52
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833222
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Tactical Nuclear Penguinты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...

Это не важно..
Цель была оценить распараллеливание по виртуальным процессорам.
...
Рейтинг: 0 / 0
03.07.2019, 12:54
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833270
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

То есть вы не видите проблемы?

Озвучите
...
Рейтинг: 0 / 0
03.07.2019, 13:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833281
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
black-manatee,

оставим, что ради сортировки нужно в приложение притащить БД
пойдем дальше
ТС пишет что исходный вариант (сортировка в памяти) работает, но медленно
для примера возьмем результат X-Cite, у него сортировка заняла 10 сек
для начала сравните, плз, сколько у вас займет "загнять массив строк в таличку"
...
Рейтинг: 0 / 0
03.07.2019, 13:59
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833363
black-manatee
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
black-manatee
Гость
Дегтярев Евгенийblack-manatee,

оставим, что ради сортировки нужно в приложение притащить БД
пойдем дальше
ТС пишет что исходный вариант (сортировка в памяти) работает, но медленно
для примера возьмем результат X-Cite, у него сортировка заняла 10 сек
для начала сравните, плз, сколько у вас займет "загнять массив строк в таличку"

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

Но вообще речь не об этом.
Человек работает с сотнями миллионов строк. Эти строки у него откуда то берутся (какие нибудь логи или что-то еще), записываются в какое-то хранилище (текстовые файлы), потом неким образом обрабатываются (сортируются и удаляются дубли), потом опять куда-то записываются (в те же или другие текстовые файлы), а затем очевидно где-то далее используются. То есть по сути речь идет о простой, но достаточно объемной БД, в качестве каковой registered использует текстовые файлы.
По моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.
...
Рейтинг: 0 / 0
03.07.2019, 15:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833405
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
black-manateeПо моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.
А мне очевидно что напрашивается ElasticSearch + Kibana
...
Рейтинг: 0 / 0
03.07.2019, 16:01
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833412
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Кстати, TArray.Sort сортирует в другом порядке, нежели StringList.
Пока что получилось, TArray где-то в 2 раза быстрее.

3327471 записей (98.1 мб)
25,125 сек - сорт StringList после загрузки
13,953 сек - сорт TArray<ansistring>

TArray - это то же самое, что и array of string? Мне этот синтаксис непривычен. Чем он хорош? Тем, что там есть Sort? А что мешало сделать отдельную функцию Sort для массива?
...
Рейтинг: 0 / 0
03.07.2019, 16:12
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833426
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
http://docwiki.embarcadero.com/Libraries/Rio/en/System.Generics.Collections.TArray

Это просто удобная обертка для статических дженериковских функций
...
Рейтинг: 0 / 0
03.07.2019, 16:26
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833430
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Ну и сам тип конечно...
http://docwiki.embarcadero.com/Libraries/Rio/en/System.TArray
...
Рейтинг: 0 / 0
03.07.2019, 16:28
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833528
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
StringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?
...
Рейтинг: 0 / 0
03.07.2019, 19:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833531
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registered,

AnsiUpperCase.
...
Рейтинг: 0 / 0
03.07.2019, 19:28
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833550
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Там (в StringList) даже не посимвольно сравнивает, а, к примеру,
test031
и
test-03-1
будут вперемешку.

 
function TStringList.CompareStrings(const S1, S2: string): Integer;
begin
if CaseSensitive then
Result := AnsiCompareStr(S1, S2)
else
Result := AnsiCompareText(S1, S2);
end;


Добавил свой компаратор, такой:

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
    comparer: IComparer<ansistring>;

      comparer := TDelegatedComparer<ansistring>.Create
       (
         function(const Left, Right: ansistring): Integer
         begin
            Result := AnsiCompareStr(Left,Right);
         end
      );

TArray.Sort<ansistring>(tarrstr,comparer);



Теперь сортирует так же, как StringList, но в 3 раза медленнее.
StringList - 9,641 сек
TArray.Sort (comparer) - 25,859 сек
TArray.Sort (по умолчанию) - 4,234 сек

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

И зачем я всё это делал?
...
Рейтинг: 0 / 0
03.07.2019, 20:59
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833552
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
registeredИ зачем я всё это делал?Получил ценный опыт.
...
Рейтинг: 0 / 0
03.07.2019, 21:17
| Ответить | Цитировать | Написать  
25 сообщений из 55, страница 1 из 3
  1  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39833531&tid=2039285]:
 0ms
get settings:
 9ms
get forum list:
 19ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 409ms
get topic data:
 5ms
get forum data:
 2ms
get page messages:
 36ms
get tp. blocked users:
 1ms
others: 229ms
total:  716ms
созд. / загр.: 716ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]