ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
25 сообщений из 55, страница 2 из 3
  2  все
Сортировка сотен миллионов строк с удалением дублей
    #39833553
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
registered,

авторТеперь сортирует так же, как StringList, но в 3 раза медленнее.
мода требует жертв.
...
Рейтинг: 0 / 0
03.07.2019, 21:18
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833554
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
registeredТеперь сортирует так же, как StringList, но в 3 раза медленнее.
В одном случае сортируешь String, в другом AnsiString получаемые в результате конвертирования из String. Отсюда и просадка такая.
...
Рейтинг: 0 / 0
03.07.2019, 21:29
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833557
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Kazantsev Alexeyполучаемые в результате конвертирования из String
...наоборот, в смысле. Короче, замени AnsiString на String везде.
...
Рейтинг: 0 / 0
03.07.2019, 21:39
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833593
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Со String - 10,297 сек

Хотя уже переделал обратно в StringList
...
Рейтинг: 0 / 0
03.07.2019, 23:23
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39833647
Фотография X11
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X11
Участник
registeredStringList сортирует так, что одинаковые записи, различающиеся строчными и прописными буквами, будут соседними, а TArray - по коду символа, т.е., они будут в разных местах. Можно ли сделать, чтобы по-другому?

Думаю TDictionary тебя спасёт
...
Рейтинг: 0 / 0
04.07.2019, 09:04
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834311
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
Kazantsev AlexeyKazantsev Alexeyполучаемые в результате конвертирования из String
...наоборот, в смысле. Короче, замени AnsiString на String везде.А почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
...
Рейтинг: 0 / 0
05.07.2019, 12:30
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834315
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
registeredА почему с System.AnsiStrings.AnsiCompareStr медленно? Тогда не должно конвертироваться в String.
Насколько я помню, всё современное API винды уже давно юникодовое, а когда используются старые вызовы (с суфиксом A) то внутри происходит преобразование в юникод и последующий вызов нужного юникодового метода. Таким образом, преобразование строк просто переносится на уровень системы.
...
Рейтинг: 0 / 0
05.07.2019, 12:38
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834506
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Я тут тест проводил

 
код теста
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
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.10GHzIntel(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.20GHzIntel(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.40GHzIntel(R) Xeon(R) CPU E5-4640 0 @ 2.40GHz
Сокетов: 4
Виртуальные процессоры: 16
Виртуальная машина: Да
Кэш L1: Н/Д

1 = 41553 мс (В 1 поток)
16 = 13800 мс (В 16 потоков = кол-во виртуальных процессоров)
...
Рейтинг: 0 / 0
05.07.2019, 23:24
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834508
registered
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
registered
Гость
А разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
...
Рейтинг: 0 / 0
05.07.2019, 23:32
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834509
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
softwarer
Участник
registeredА разделение как реализовано? Если разделить массив на X частей, и каждую отсортировать, а потом слить, то он будет неотсортированным.
Merge sort уже отменили?
...
Рейтинг: 0 / 0
05.07.2019, 23:33
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834511
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
Кстати... Можно сделать merge sort и проверить результат...

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

По сути:
1) Делим 1 массив на N - выполняется в одном потоке
2) Сортируем N частей в N тасках. При этом надеемся TThreadPool корректно их распихал в N потоков. А ОС корректно их разнесла по процессорам/ядрам.
3) Ждем всех, чтобы сделать merge join
4) Делаем merge join из N массивов в 1.
...
Рейтинг: 0 / 0
05.07.2019, 23:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834534
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
white_nigger
Участник
X-Cite,

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

1 = 11641
8 = 3126

i7-4710HQ 2.5GHz
...
Рейтинг: 0 / 0
06.07.2019, 01:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834543
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
registered,

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

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

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

Если дубликатов много - лучше сработает первый способ. Если мало - второй. Можно извратиться и взять Rapid.Generics - там сортировки и словари быстрее.
...
Рейтинг: 0 / 0
06.07.2019, 07:52
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834544
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
Голландец,

Наоборот. Дубликатов мало - первый способ. Много - словари )
...
Рейтинг: 0 / 0
06.07.2019, 07:55
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834547
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Вообще-то, у TStringList есть свойство Duplicates, которое можно выставить в dupIgnore. Также у него есть свойство Capacity.
...
Рейтинг: 0 / 0
06.07.2019, 08:56
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834559
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
registered,

сколько у тебя различных строк после отсева дубликатов в реальных данных?
...
Рейтинг: 0 / 0
06.07.2019, 10:46
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834586
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
white_nigger,

Потому что на коленке писаная за 10 минут для этого топика)
...
Рейтинг: 0 / 0
06.07.2019, 13:14
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834606
MaratIsk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MaratIsk
Участник
registered,

чо-то 100 лямов мало :(
надо не ниже 3,5 лярдов, а лучше 5 (с запасом, так сказать)
...
Рейтинг: 0 / 0
06.07.2019, 14:29
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834706
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
white_nigger
Участник
X-Cite,
Понятно. Кстати, возможно у меня использовались только 4 ядра. Надо будет по коду глянуть. Я уже не помню как рассчитывал количество потоков
...
Рейтинг: 0 / 0
07.07.2019, 13:04
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834720
Фотография X-Cite
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
X-Cite
Участник
white_niggerX-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 и давай его везде пихать...
...
Рейтинг: 0 / 0
07.07.2019, 15:02
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834729
Голландец
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Голландец
Участник
X-Cite,

QuickSort на выходе может дать 2 диапазона. Один можно продолжить выполнять в том же потоке, а второй - отдать в пул. Тогда не придётся делать мердж.
...
Рейтинг: 0 / 0
07.07.2019, 15:34
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834734
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Поскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна. Хэш-таблица
даёт тот же результат, но имеет O(1) вместо O(N*log2(N)).
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
07.07.2019, 16:15
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834737
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Dimitry SibiryakovПоскольку задача исключительно на дубликаты, сортировка тут напрочь не нужна.
Хм...
https://www.sql.ru/forum/actualutils.aspx?action=gotomsg&tid=1314494&msg=21919544 А вообще, мне нужно отсортировать несколько (сотен) миллионов строк, удалив одинаковые.
...
Рейтинг: 0 / 0
07.07.2019, 16:17
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834755
Фотография Дегтярев Евгений
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дегтярев Евгений
Участник
> Все 24 лп не напрягались, ощущение что уперлось во что-то другое, возможно память.
NUMA?
...
Рейтинг: 0 / 0
07.07.2019, 17:43
| Ответить | Цитировать | Написать  
Сортировка сотен миллионов строк с удалением дублей
    #39834816
Фотография Критик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Критик
Участник
1) проанализировать, откуда эти строки, собственно, берутся, может проще исключить возникновение дублей
2) проанализировать задачу, можно ли ее решить в другом слое приложения - в той же упомянутой СУБД
3) если ничего не поучилось, то сортировать в приложении, но это поражение
...
Рейтинг: 0 / 0
07.07.2019, 23:48
| Ответить | Цитировать | Написать  
25 сообщений из 55, страница 2 из 3
  2  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Сортировка сотен миллионов строк с удалением дублей
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39834737&tid=2039285]:
 0ms
get settings:
 6ms
get forum list:
 11ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 167ms
get topic data:
 7ms
get forum data:
 2ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 226ms
total:  465ms
созд. / загр.: 465ms
x
x
Закрыть


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