Самая быстрая сортировка для мало отличающихся строк

@Etyuhibosecyu · Регистрация: 13.07.2017

Студворк — интернет-сервис помощи студентам

Кто знает, как ее реализовать? Классическая быстрая сортировка (Хоара) для этого не подходит, потому что у нее много времени уходит на посимвольное сравнение, и вместо n*log(n) ее сложность n^2*log(n) - на сортировку 1000 строк из 1000 символов уйдет 10 миллионов операций - если считать, что одна занимает 100 микросекунд, вся сортировка займет 17 минут. Существует ли какая-либо сортировка, адаптированная именно для строк?

@kolorotur · 28.02.2019, 13:54

Алгоритм сортировки и алгоритм сравнения — разные вещи, один на другой влияет не сильно.
Можете реализовать свой супер-быстрый компарер, который и передавать в алгоритм сортировки.

Добавлено через 7 минут

Сообщение от Etyuhibosecyu

на сортировку 1000 строк из 1000 символов уйдет 10 миллионов операций - если считать, что одна занимает 100 микросекунд, вся сортировка займет 17 минут.

А откуда взялась такая конская цифра в 100 мкс на одно сравнение?

Вот простой тест, который сортирует 1000 строк длиной в 1000 символов, различающихся только последним символом:

C#
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
using System;
using System.Collections.Generic;
using System.Diagnostics;
 
class Program
{
    static void Main()
    {
        var chars = RandomChars(1000);
        var strings = new List<string>();
 
        for (int i = 0; i < 1000; i++)
        {
            chars[chars.Length - 1] = (char)rand.Next(32, 127);
            strings.Add(new string(chars));
        }
 
        var sw = Stopwatch.StartNew();
        strings.Sort();
        sw.Stop();
 
        Console.WriteLine(sw.Elapsed);
    }
 
    static readonly Random rand = new Random();
    static char[] RandomChars(int length)
    {
        var chars = new char[length];
        for (int i = 0; i < chars.Length; i++)
            chars[i] = (char)rand.Next(32, 127);
        return chars;
    }
}

На моей старенькой системе занимает где-то 17мс.

@Etyuhibosecyu · 28.02.2019, 14:01 **[ТС]**

А откуда взялась функция strings.Sort()? Если там, к примеру, не строки, а сложные классы, как она себя поведет?

Добавлено через 1 минуту
А мне нужно именно со сложными классами, строки это просто как упрощенная модель.

@kolorotur · 28.02.2019, 14:04

Сообщение от Etyuhibosecyu

А откуда взялась функция strings.Sort()?

Переменная strings имеет тип List<string>, в классе List<T> имеется метод Sort, реализующий гибридный метод сортировки (в доках по ссылке описаны детали).

Сообщение от Etyuhibosecyu

Если там, к примеру, не строки, а сложные классы, как она себя поведет?

Попытается отсортировать, используя дефолтный компарер для этого класса.
Если такового не найдено, то выбросит исключение.

У метода есть несколько перегрузок, позволяющих передавать свою реализацию сравнения либо в виде ссылки на метод, либо в виде реализации интерфейса IComparer<T>.

@Etyuhibosecyu · 28.02.2019, 14:11 **[ТС]**

Допустим, у меня есть 1000 двумерных списков, в каждом из которых 1000 одномерных списков, в каждом из которых от одного до трех классов, представляющих собой пару uint. И, к примеру, нужно выполнить такую сортировку 4000 раз. Суток хватит на это?

Добавлено через 1 минуту
Если очень важно, что это за задача - отвечу: BWT для "Властелина колец" (яркий пример большого осмысленного текста на естественном языке, "Войны и мира" у меня нет).

@kolorotur · 28.02.2019, 14:12

Сообщение от Etyuhibosecyu

у меня есть 1000 двумерных списков, в каждом из которых 1000 одномерных списков, в каждом из которых от одного до трех классов, представляющих собой пару uint.

Может, на данном этапе лучше стоит задуматься об организации структур данных, используемых в своем коде?

Сообщение от Etyuhibosecyu

нужно выполнить такую сортировку 4000 раз

"Такую" — это какую? Вытащить из всех этих списков все элементы и отсортировать их как один список?

@Etyuhibosecyu · 28.02.2019, 14:19 **[ТС]**

Да, и такие пары uint генерируются авторской версией Хаффмана.

Сообщение от kolorotur

стоит задуматься об организации структур данных, используемых в своем коде?

Объясните подробнее.

Добавлено через 5 минут

Сообщение от kolorotur

"Такую" — это какую? Вытащить из всех этих списков все элементы и отсортировать их как один список?

Нет, вся фишка в том, что двумерный список - циклическая перестановка, одномерный - генерируется моей версией Хаффмана из символа, три пары uint - для частых и редких символов, частые - одна, умеренно редкие - две, очень редкие - три. И все двумерные списки должны сохранить свой состав и быть отсортированными именно как цельные классы.

@kolorotur · 28.02.2019, 14:21

Сообщение от Etyuhibosecyu

се двумерные списки должны сохранить свой состав и быть отсортированными именно как цельные классы.

Так что конкретно сортируется-то? Просто пары в этих списках?
Приведите пример данных до такой сортировки и после.
Не обязательно 1000000 элементов создавать

@Etyuhibosecyu · 28.02.2019, 14:38 **[ТС]**

Ну, например: { { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }, { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }, { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } }, { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }, { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } } }. После сортировки: { { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } }, { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }, { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }, { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }, { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } } }. Сначала взят список, начинающийся с (10, 1), затем с (10, 5) и т. д. Простите за кричащее выделение, это чтобы было понятнее - разные части разным выделением.

Добавлено через 2 минуты
Да, одинаково не получилось выразительно...

@kolorotur · 28.02.2019, 14:38

Что-то не улавливаю логику сравнения.

@Etyuhibosecyu · 28.02.2019, 14:49 **[ТС]**

Попробую так - первый по алфавиту элемент жирным, последний - курсивом:
До сортировки:
1. { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }
2. { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }
3. { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }[/I] }
4. { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }
5. { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } }
После сортировки:
1. { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } }
2. { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }
3. { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }
4. { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }
5. { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } }
По возрастанию второго числа в первой паре первого списка, где оно отличается. То есть:
1. Возрастание списков.
2. Возрастание количества элементов в одномерных списках.
3. Возрастание второго числа в первом отличающемся элементе.

Добавлено через 1 минуту
Реально ли как-то, следуя этой логике, написать более быстрый компаратор, чем сравнение всех значений?

@Элд Хасп · 28.02.2019, 19:43

Сообщение от Etyuhibosecyu

По возрастанию второго числа в первой паре первого списка, где оно отличается.

Если правильно Вас понял, то у Вас такой трёхуровневый набор элементов

Ienumerable<Ienumerable<Ienumerable<(int first, int second)>>>

И сортировку надо сделать первого уровня по второму числу третьего уровня

var sort = sorce.OrderBy(el => el.First().First().second);

Где sorce исходный набор указанного типа.

@Etyuhibosecyu · 28.02.2019, 19:45 **[ТС]**

Элд Хасп, тема больше не актуальна, можно закрывать. Думаю, в сутки уложусь.

@Элд Хасп · 28.02.2019, 19:46

Сообщение от Etyuhibosecyu

1. Возрастание списков.
2. Возрастание количества элементов в одномерных списках.
3. Возрастание второго числа в первом отличающемся элементе.

Не понятно.
В Вашем примере только третий пункт.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Программа принимает математическое выражение в виде строки и выдаёт его производную в виде строки и вычисляет значение производной при заданном х Логарифм записывается как: (x-2)log(x^2+2) -. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14

	Самая быстрая сортировка для мало отличающихся строк 28.02.2019, 13:16. Показов 1358. Ответов 13 Метки нет (Все метки) Кто знает, как ее реализовать? Классическая быстрая сортировка (Хоара) для этого не подходит, потому что у нее много времени уходит на посимвольное сравнение, и вместо nlog(n) ее сложность n^2log(n) - на сортировку 1000 строк из 1000 символов уйдет 10 миллионов операций - если считать, что одна занимает 100 микросекунд, вся сортировка займет 17 минут. Существует ли какая-либо сортировка, адаптированная именно для строк? 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14
	28.02.2019, 14:01 [ТС]
	А откуда взялась функция strings.Sort()? Если там, к примеру, не строки, а сложные классы, как она себя поведет? Добавлено через 1 минуту А мне нужно именно со сложными классами, строки это просто как упрощенная модель. 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14
	28.02.2019, 14:11 [ТС]
	Допустим, у меня есть 1000 двумерных списков, в каждом из которых 1000 одномерных списков, в каждом из которых от одного до трех классов, представляющих собой пару uint. И, к примеру, нужно выполнить такую сортировку 4000 раз. Суток хватит на это? Добавлено через 1 минуту Если очень важно, что это за задача - отвечу: BWT для "Властелина колец" (яркий пример большого осмысленного текста на естественном языке, "Войны и мира" у меня нет). 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14
	28.02.2019, 14:38 [ТС]
	*Ну, например:* { { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }, { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }, { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } }, { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }, { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } } }. *После сортировки:* { { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } }, { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } }, { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } }, { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } }, { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } } }. Сначала взят список, начинающийся с (10, 1), затем с (10, 5) и т. д. Простите за кричащее выделение, это чтобы было понятнее - разные части разным выделением. Добавлено через 2 минуты Да, одинаково не получилось выразительно... 0

@kolorotur 17823 / 12973 / 3382 Регистрация: 17.09.2011 Сообщений: 21,261
	28.02.2019, 14:38
	Что-то не улавливаю логику сравнения. 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14
	28.02.2019, 14:49 [ТС]
	Попробую так - первый по алфавиту элемент жирным, последний - курсивом: До сортировки: 1. { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } } 2. { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } } 3. { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }[/I] } 4. { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } } 5. { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } } После сортировки: 1. { { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) } } 2. { { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) } } 3. { { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) } } 4. { { (10, 8), (21, 0) }, { (10, 5) }, { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) } } 5. { { (10, 8), (21, 20), (36, 11) }, { (10, 7) }, { (10, 1) }, { (10, 8), (21, 0) }, { (10, 5) } } По возрастанию второго числа в первой паре первого списка, где оно отличается. То есть: 1. Возрастание списков. 2. Возрастание количества элементов в одномерных списках. 3. Возрастание второго числа в первом отличающемся элементе. Добавлено через 1 минуту Реально ли как-то, следуя этой логике, написать более быстрый компаратор, чем сравнение всех значений? 0

@Etyuhibosecyu Труд вопреки насмешкам 430 / 181 / 41 Регистрация: 13.07.2017 Сообщений: 4,627 Записей в блоге: 14
	28.02.2019, 19:45 [ТС]
	Элд Хасп, тема больше не актуальна, можно закрывать. Думаю, в сутки уложусь. 0