Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
А что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые. Пока StringList с Sorted=true работает, но, возможно, медленно. Можно ли сделать что-то принципиально быстрее?
Использую несколько StringList'ов, чтобы разные записи, например, начинающиеся на разные буквы, сохранять в разных StringList'ах. Так, наверно, быстрее (сортировать несколько маленьких, чем один большой).
3 июл 19, 02:17    [21919544]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
black-manatee
Member

Откуда:
Сообщений: 50
registered
А что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

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

В Вашем случае прямо таки напрашивается использование какой нибудь СУБД. Возможно встроенной, например SQLite или Firebird embedded.

Загоняете массив строк в табличку, а далее уже SQL выражениями делаете любую выборку. Все современные СУБД делают это очень быстро.
3 июл 19, 06:54    [21919562]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1679
black-manatee,

СУБД?
Ради сортировки строк?
Реально?
3 июл 19, 10:12    [21919619]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
rgreat
Member

Откуда:
Сообщений: 5359
registered,

Быстрей можно всегда, только это ручками делать надо.
Например побить свой лист на много более мелких. Так сортировка будет работать значительно быстрей.
3 июл 19, 10:34    [21919640]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5192
registered
А что такое TStringList? Это массив строк? Он непрерывно хранится в памяти? Что происходит, если добавляешь элемент, например, в середину? А если несколько StringList'ов, и попеременно добавлять и туда, и сюда, то они фрагментируются? Или полностью копируется весь StringList на новое место?

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

метод сортировки в узких случаях нужно подбирать индивидуально, реализация сортировки в TSringList от дельфи, редкий позор
+ сортировка Хаора очень чувствительна к функции сравнения
3 июл 19, 11:10    [21919661]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
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 распараллелить по кускам и потом склеить, будет быстрее в зависимости от кол-ва ядер и процессоров.
3 июл 19, 11:30    [21919678]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
Я тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

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

заняло 5 секунд
3 июл 19, 11:54    [21919704]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5192
X-Cite,

вся беда таких тестов что они не учитывают реальные данные и особенности алгоритмов
3 июл 19, 12:03    [21919709]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Tactical Nuclear Penguin
Member

Откуда: холодно тут
Сообщений: 2702
X-Cite
Я тут на коленке накидал распараллеливание, получил на 10 млн строк на 1 процессоре и 4 ядрах
в 1 поток заняло 10 секунд

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

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


ты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...
3 июл 19, 12:05    [21919713]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
black-manatee
Member

Откуда:
Сообщений: 50
Дегтярев Евгений
black-manatee,

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


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

А в чем собственно проблема ?
3 июл 19, 12:34    [21919746]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
rgreat
Member

Откуда:
Сообщений: 5359
А можно еще хешик сделать. На первые несколько букв строки.
И сортировать по хэшу.
3 июл 19, 12:42    [21919752]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1679
black-manatee,

То есть вы не видите проблемы?
3 июл 19, 12:43    [21919755]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 58902
Блог
black-manatee
Сортировка с выкидыванием дублей. TStringList так вроде не умеет.

Да ну правда что ли?
3 июл 19, 12:52    [21919762]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
Tactical Nuclear Penguin
ты бы на нормальных строках делал, длиной хотя бы 50 знаков и из букв...


Это не важно..
Цель была оценить распараллеливание по виртуальным процессорам.
3 июл 19, 12:54    [21919767]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
black-manatee
Member

Откуда:
Сообщений: 50
Дегтярев Евгений
black-manatee,

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


Озвучите
3 июл 19, 13:43    [21919830]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1679
black-manatee,

оставим, что ради сортировки нужно в приложение притащить БД
пойдем дальше
ТС пишет что исходный вариант (сортировка в памяти) работает, но медленно
для примера возьмем результат X-Cite, у него сортировка заняла 10 сек
для начала сравните, плз, сколько у вас займет "загнять массив строк в таличку"
3 июл 19, 13:59    [21919846]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
black-manatee
Member

Откуда:
Сообщений: 50
Дегтярев Евгений
black-manatee,

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


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

Но вообще речь не об этом.
Человек работает с сотнями миллионов строк. Эти строки у него откуда то берутся (какие нибудь логи или что-то еще), записываются в какое-то хранилище (текстовые файлы), потом неким образом обрабатываются (сортируются и удаляются дубли), потом опять куда-то записываются (в те же или другие текстовые файлы), а затем очевидно где-то далее используются. То есть по сути речь идет о простой, но достаточно объемной БД, в качестве каковой registered использует текстовые файлы.
По моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.
3 июл 19, 15:17    [21919966]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
black-manatee
По моему очевидно, что использование СУБД в данном случае для всей этой байды реально напрашивается.

А мне очевидно что напрашивается ElasticSearch + Kibana
3 июл 19, 16:01    [21920030]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
Кстати, TArray.Sort сортирует в другом порядке, нежели StringList.
Пока что получилось, TArray где-то в 2 раза быстрее.

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

TArray - это то же самое, что и array of string? Мне этот синтаксис непривычен. Чем он хорош? Тем, что там есть Sort? А что мешало сделать отдельную функцию Sort для массива?
3 июл 19, 16:12    [21920039]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
http://docwiki.embarcadero.com/Libraries/Rio/en/System.Generics.Collections.TArray

Это просто удобная обертка для статических дженериковских функций
3 июл 19, 16:26    [21920057]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1578
Ну и сам тип конечно...
http://docwiki.embarcadero.com/Libraries/Rio/en/System.TArray
3 июл 19, 16:28    [21920061]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
StringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?
3 июл 19, 19:15    [21920217]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
rgreat
Member

Откуда:
Сообщений: 5359
registered,

AnsiUpperCase.
3 июл 19, 19:28    [21920222]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
Там (в 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;


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

    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 сек

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

И зачем я всё это делал?
3 июл 19, 20:59    [21920258]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
rgreat
Member

Откуда:
Сообщений: 5359
registered
И зачем я всё это делал?
Получил ценный опыт.
3 июл 19, 21:17    [21920261]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Delphi Ответить