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

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

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

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

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

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

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

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

Откуда: Минск
Сообщений: 1579
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

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

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

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

Откуда: Нижневартовск
Сообщений: 5211
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

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

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

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

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

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

Откуда: Минск
Сообщений: 1579
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

Откуда: Барнаул
Сообщений: 1684
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

Откуда: Минск
Сообщений: 1579
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

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

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

Откуда: Минск
Сообщений: 1579
Ну и сам тип конечно...
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

Откуда:
Сообщений: 5381
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

Откуда:
Сообщений: 5381
registered
И зачем я всё это делал?
Получил ценный опыт.
3 июл 19, 21:17    [21920261]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
makhaon
Member

Откуда: A galaxy far far away
Сообщений: 3356
registered,

автор
Теперь сортирует так же, как StringList, но в 3 раза медленнее.

мода требует жертв.
3 июл 19, 21:18    [21920262]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3820
registered
Теперь сортирует так же, как StringList, но в 3 раза медленнее.

В одном случае сортируешь String, в другом AnsiString получаемые в результате конвертирования из String. Отсюда и просадка такая.
3 июл 19, 21:29    [21920264]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3820
Kazantsev Alexey
получаемые в результате конвертирования из String

...наоборот, в смысле. Короче, замени AnsiString на String везде.
3 июл 19, 21:39    [21920267]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
Со String - 10,297 сек

Хотя уже переделал обратно в StringList
3 июл 19, 23:23    [21920351]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X11
Member

Откуда: Kharkiv, Ukraine
Сообщений: 13300
registered
StringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?


Думаю TDictionary тебя спасёт
4 июл 19, 09:04    [21920452]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
Kazantsev Alexey
Kazantsev Alexey
получаемые в результате конвертирования из String

...наоборот, в смысле. Короче, замени AnsiString на String везде.
А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
5 июл 19, 12:30    [21921518]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3820
registered
А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.

Насколько я помню, всё современное API винды уже давно юникодовое, а когда используются старые вызовы (с суфиксом A) то внутри происходит преобразование в юникод и последующий вызов нужного юникодового метода. Таким образом, преобразование строк просто переносится на уровень системы.
5 июл 19, 12:38    [21921523]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
Я тут тест проводил

+ код теста
procedure Test;
const
  N = 10000000;
var
  Basis, Basis2: TArray<string>;
  k: Int32;
  sw: TStopwatch;

  function GetStr(const aLength: Int32): string;
  var
    k: Int32;
  begin
    SetLength(Result, aLength);
    for k := 1 to aLength do
      Result[k] := Chr(Random(150) + 32);
  end;

begin
  Randomize();
  SetLength(Basis, N);
  for k := Low(Basis) to High(Basis) do
    Basis[k] := GetStr(Random(50) + 20);
  SetLength(Basis2, N);
  TArray.Copy<string>(Basis, Basis2, N);

  sw := TStopwatch.StartNew();
  TArray.Sort<string>(Basis);
  sw.Stop();
  Memo1.Lines.Add('1 = ' + sw.ElapsedMilliseconds.ToString());

  sw := TStopwatch.StartNew();
  SortFast(Basis2); // Реализация на коленке разделения сортировки на X (где X = TThread.ProcessorCount) частей, где каждая часть использует TArray.Sort
  sw.Stop();
  Memo1.Lines.Add(TThread.ProcessorCount.ToString() + ' = ' + sw.ElapsedMilliseconds.ToString());
end;



+ Intel(R) Core(TM) i5-8600 CPU @ 3.10GHz
Intel(R) Core(TM) i5-8600 CPU @ 3.10GHz
Сокетов: 1
Ядра: 6
Логических процессоров: 6
Виртуализация: Включено
Кэш L1: 384 КБ
Кэш L2: 1,5 МБ
Кэш L3: 9,0 МБ

1 = 8817 мс (В 1 поток)
6 = 4388 мс (В 6 потоков = кол-во логических процессоров)


+ Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz
Intel(R) Xeon(R) Gold 6146 CPU @ 3.20GHz
Сокетов: 2
Ядра: 24
Логических процессоров: 24
Виртуализация: Отключено
Поддержка Hyper-V: Да
Кэш L1: 1,5 МБ
Кэш L2: 24,0 МБ
Кэш L3: 49,5 МБ

1 = 13992 мс (В 1 поток)
24 = 7560 мс (В 24 потока = кол-во логических процессоров)
Здесь был интересный момент. Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.


+ Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
Intel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
Сокетов: 4
Виртуальные процессоры: 16
Виртуальная машина: Да
Кэш L1: Н/Д

1 = 41553 мс (В 1 поток)
16 = 13800 мс (В 16 потоков = кол-во виртуальных процессоров)
5 июл 19, 23:24    [21921854]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
registered
Member

Откуда:
Сообщений: 64
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
5 июл 19, 23:32    [21921861]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
softwarer
Member

Откуда: 127.0.0.1
Сообщений: 58933
Блог
registered
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.

Merge sort уже отменили?
5 июл 19, 23:33    [21921862]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
Кстати... Можно сделать merge sort и проверить результат...

Потому что моя цель была разделить именно на N частей и сделать TArray.Sort каждой части в своей таске, а потом их склеить через merge join

По сути:
1) Делим 1 массив на N - выполняется в одном потоке
2) Сортируем N частей в N тасках. При этом надеемся TThreadPool корректно их распихал в N потоков. А ОС корректно их разнесла по процессорам/ядрам.
3) Ждем всех, чтобы сделать merge join
4) Делаем merge join из N массивов в 1.
5 июл 19, 23:43    [21921869]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 2202
X-Cite,

Что-то у тебя плохо масштабируется по ядрам. Сейчас проверил твой пример на своей версии из dxThreading на своем ноуте:

1 = 11641
8 = 3126

i7-4710HQ 2.5GHz
6 июл 19, 01:15    [21921898]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

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

Ты не послушаешь, но это правда самые быстрые способы.

1. Добавить строки в TStringList(а лучше в динамический массив, предварительно установив длину). Отсортировать. Пройтись от последнего к первому и удалить дубликаты. Есть более продвинутый способ удаления дубликатов, но ты его, скорее всего не потянешь )

2. Сделать TDictionary и выполнять AddOrSetValue. Потом сделать ToArray и отсортировать массив.

Если дубликатов много - лучше сработает первый способ. Если мало - второй. Можно извратиться и взять Rapid.Generics - там сортировки и словари быстрее.
6 июл 19, 07:52    [21921914]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

Откуда:
Сообщений: 122
Голландец,

Наоборот. Дубликатов мало - первый способ. Много - словари )
6 июл 19, 07:55    [21921915]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3820
Вообще-то, у TStringList есть свойство Duplicates, которое можно выставить в dupIgnore. Также у него есть свойство Capacity.
6 июл 19, 08:56    [21921922]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1771
registered,

сколько у тебя различных строк после отсева дубликатов в реальных данных?
6 июл 19, 10:46    [21921951]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
white_nigger,

Потому что на коленке писаная за 10 минут для этого топика)
6 июл 19, 13:14    [21921997]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
MaratIsk
Member

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

чо-то 100 лямов мало :(
надо не ниже 3,5 лярдов, а лучше 5 (с запасом, так сказать)
6 июл 19, 14:29    [21922021]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 2202
X-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков
7 июл 19, 13:04    [21922214]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
white_nigger
X-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков

Я не думал, просто взял кол-во задач = кол-ву логических процессоров, хотя можно поиграться...
Параллелилось норм... я же merge сделал в основном потоке, не параллелил его и в лоб к тому же, а не по книжке....
Да и копирование можно было сделать в своем чанке... еще 100 мс сэкономить...

19368 - основной поток

07.07.2019 14:58:59.747; 19368: ->Run
07.07.2019 14:58:59.887; 19368: Copy = 125
07.07.2019 14:59:01.846; 5472: Chunk1 = 1958
07.07.2019 14:59:01.876; 16680: Chunk2 = 1989
07.07.2019 14:59:01.888; 5364: Chunk3 = 2006
07.07.2019 14:59:01.896; 10712: Chunk4 = 2011
07.07.2019 14:59:01.896; 12284: Chunk5 = 2014
07.07.2019 14:59:01.922; 15260: Chunk6 = 2037
07.07.2019 14:59:01.922; 19368: All wait = 2037
07.07.2019 14:59:04.259; 19368: merge = 2338
07.07.2019 14:59:04.259; 19368: <-Run

Основной посыл был в том, что даже на коленке наспех реализация распараллеливания сортировки выгоднее.
А не прочитали в книжке 199x года, что есть вот такой "замечательный" TStringList и давай его везде пихать...
7 июл 19, 15:02    [21922238]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Голландец
Member

Откуда:
Сообщений: 122
X-Cite,

QuickSort на выходе может дать 2 диапазона. Один можно продолжить выполнять в том же потоке, а второй - отдать в пул. Тогда не придётся делать мердж.
7 июл 19, 15:34    [21922247]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 48414

Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна. Хэш-таблица
даёт тот же результат, но имеет O(1) вместо O(N*log2(N)).

Posted via ActualForum NNTP Server 1.5

7 июл 19, 16:15    [21922253]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 3820
Dimitry Sibiryakov
Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна.

Хм...
https://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1314494&msg=21919544
А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые.
7 июл 19, 16:17    [21922256]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1684
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
7 июл 19, 17:43    [21922278]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Критик
Member

Откуда: Москва / Калуга
Сообщений: 32263
Блог
1) проанализировать, откуда эти строки, собственно, берутся, может проще исключить возникновение дублей
2) проанализировать задачу, можно ли ее решить в другом слое приложения - в той же упомянутой СУБД
3) если ничего не поучилось, то сортировать в приложении, но это поражение
7 июл 19, 23:48    [21922367]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
Дегтярев Евгений
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?

Да
8 июл 19, 09:33    [21922461]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Gator
Member

Откуда: Москва
Сообщений: 14978
X-Cite
Дегтярев Евгений
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?

Да

Вроде бы Тема о сортировке большых(?) объёмах данных? На клиенте?
А вы тут... PUMA зачем-то... Вы бы ещё IBM & Cray Corp вспомнили...
SAS мозгололомоы разбежались по конторам по тематике...
___
Собственно вопрос. Кто в состоянии обработать 100 миллионов строк (а завтра и 100 миллиардов)?
Тут нужен сервис ленивый (а ля LazyReader/LazyWriter)
Клиенту-то это зачем?
Распределённая сеть с распределёнными транзакциями ради тупой сортировки(?) неизвестно чего(ТС?)???
Да ещё на Дельфи? Не верю!

Клиент пусть берёт нужную выборку из своего OLAP и сортирует,
как жопса скажет нужные ему поля в нужном ему порядке
______________
Картинка с другого сайта.Картинка с другого сайта.Картинка с другого сайта.
9 июл 19, 00:23    [21923139]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Дегтярев Евгений
Member

Откуда: Барнаул
Сообщений: 1684
Gator
А вы тут... PUMA зачем-то...

whaat?
9 июл 19, 07:34    [21923177]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
Gator
Member

Откуда: Москва
Сообщений: 14978
Дегтярев Евгений,
Pardon, NUMA
9 июл 19, 11:23    [21923282]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка сотен миллионов строк с удалением дублей  [new]
X-Cite
Member

Откуда: Минск
Сообщений: 1579
Gator,

В первом сообщении был затронут общий вопрос сортировки, неважно где.
Меня же клиентские машины вообще не интересуют, у нас вся логика в бэкэнде на сервисах. Поэтому и рассматриваю этот вопрос исключительно на серверной части.

К тому же в своих тестах привел кейс для своей машины, считай клиентской, и для двух разных серверов. Моя выиграла из-за того что частота CPU выше, хотя я пробовал на физическом сервере с такой же частотой и он все равно медленнее оказался. Виртуальные серверы понятно, что проиграли.
А вопрос про NUMA возник из-за того, что меня удивило, что 24 ЛП не напрягались, и как я понял это может быть причиной, когда данные оказались в памяти не того сокета, куда прикреплен процессор.

Никакие распределенные сети не нужны. Нужно чтобы TArray.Sort<T> работал быстро неважно где и использовал все возможности машины на которой выполняется код.

P.S.
Создал в QC 3 таски:
Одна на multithreading сортировку в TArray.Sort<T> - добавить возможность включения
Одна на поддержку NUMA в менеджере памяти - актуально для бэкенда (на гитхабе нашел коммент в FastMM на поддержку, но он так и остался комментом [planned: support for multiple per-NUMA-node allocators])
Одна на поддержку NUMA в TThredPool - актуально для бэкенда
9 июл 19, 15:15    [21923501]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Delphi Ответить