Отсортировать дерево?

[OtherSide]

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

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

Все бы ничего, только в ТЗ написано, что должно работать на их данных не больше чем за 10 сек, а у меня целых 18, при том что компьютер не самый слабый - i7 2.8GH. Словарь у них специально составлен так, что бы на каждой ветке было по несколько тысяч "слов" - сочетаний символов

Пытаюсь понять, можно ли в данной задаче как-то проиндексировать или отсортировать дерево, что бы получить нужный результат?

[valchkou]

какой язык, версия ? и почему первые 10 ?

[OtherSide]

Язык - C#. Но думаю на плюсах бы не сильно отличалось. Первые 10 по условию задачи.
Но вообще как только написал пост, придумал решение. Просто кеширую результат, для слов длиной меньше N. Подобрал 5- отрабатывает меньше, чем за 1 сек

[АццкоМото]

Начинать, очевидно, надо не от начала слова, а от конца

Постановка задачи неполна - поэтому хз.

[Pantigalt]

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

...
Пытаюсь понять, можно ли в данной задаче как-то проиндексировать или отсортировать дерево, что бы получить нужный результат?

Есть несколько решений избежать полной сортировки
1. Методом разделения. Скажем если брать первые 10 максимальных (10 итераций со смещением левой границы поиска максимального на единицу вперед)
2. Использовать структуру binary heap. Сначала формируем бинарную кучу за N шагов, а потом последовательно извлекаем первые 10 элементов.

[OtherSide]

Данная задача состоит из двух частей: базовой и дополнительной. Базовая часть обязательна к решению. Дополнительная является факультативной, но, будучи решенной, может выгодно подчеркнуть знания Кандидата.

Базовая задача

Японцы бесконечно влюблены в технику, которая их окружает. Они внимательно следят за всеми техническими новинками и стараются пользоваться самыми современными и «умными» из них. У Дена и Сергея есть гениальный план: они хотят создать текстовый редактор, который покорит японцев. Важнейшей уберинтеллектуальной функцией редактора должна стать функция автодополнения. Если пользователь набрал несколько первых букв слова, редактор должен предложить ему самые правдоподобные окончания.
Ден и Сергей уже собрали огромное количество японских текстов. Для каждого слова японского языка они посчитали число раз, которое оно встречается в текстах. Если пользователь уже ввел несколько букв, то редактор должен показать не более десяти самых часто употребляемых слов, начинающихся со введенных пользователем букв, отсортированных по убыванию частоты упоминания.
Помогите Сергею с Деном перевернуть рынок текстовых редакторов.
Исходные данные
В первой строке находится единственное число N (1 ≤ N ≤ 105) — количество слов в найденных текстах. Каждая из следующих N строк содержит слово wi (непустая последовательность строчных латинских букв длиной не более 15) и целое число ni (1 ≤ ni ≤ 106) — число раз, которое встречается это слово в текстах. Слово и число разделены единственным пробелом. Ни одно слово не повторяется более одного раза. В (N + 2)-й строке находится число M (1 ≤ M ≤ 15000). В следующих M строках содержатся слова ui (непустая последовательность строчных латинских букв длиной не более 15) — начала слов, введенных пользователем.
Результат
Для каждой из M строк необходимо вывести наиболее часто употребляемые японские слова, начинающихся с ui, в порядке убывания частоты. В случае совпадения частот слова необходимо сортировать по алфавиту. Если существует больше десяти возможных вариантов, то вывести нужно лишь первые десять из них. Варианты дополнения для каждого слова необходимо разделять переводами строк.
Пример
исходные данные результат
5
kare 10
kanojo 20
karetachi 1
korosu 7
sakura 3
3
k
ka
kar kanojo
kare
korosu
karetachi

kanojo
kare
karetachi

kare
karetachi


Решение должно отвечать следующим требованиям:
• Программа должна являться консольным приложением.
• Входные данные подаются программе в стандартном потоке ввода (ввод с клавиатуры). Программа должна выводить ответ в стандартный поток вывода (вывод на экран).
• Программа должна выводить только те данные, которые требует условие задачи. Выводить приглашение для ввода («Введите N:») не нужно. Также не нужно ожидать нажатия клавиши в конце работы программы.
• Solution для VS 11, 2010 или 2008
• Код на C# в стиле, соответствующем рекомендациям http://msdn.microsoft.com/en-us/library/ms229042.aspx
• Решение должно работать быстро (не больше 1-10 секунд) на тестовом файле test.in, прилагающемся к заданию.
Дополнение
Преобразовать консольное приложение из базовой задачи в сетевой сервис и реализовать клиента для него.

Сервис обрабатывает команды вида "get <prefix>". В ответ на которые отправляет клиенту наиболее часто употребляемые слова из словаря, начинающиеся с <prefix>, в порядке убывания частоты. В случае совпадения частот слова необходимо сортировать по алфавиту. Варианты дополнения для каждого слова необходимо разделять переводами строк.

В серверном приложении реализовать поддержку нескольких одновременных клиентских соединений с эффективной многопоточностью. Эффективность измеряется значением throughput.
Ограничения на использование серверных ресурсов отсутствуют.
Сервер
Сервер — это консольное приложение, которое при старте принимает в качестве параметра
путь к текстовому файлу, содержащему словарь, и номер порта.

Клиент
Консольное приложение.
При старте принимает в качестве параметров командной строки IP адрес или hostname, а также порт сервера.

Общие требования к организации сетевого обмена
* TCP/IP v4
* Сервер должен обслуживать все соединения по заданному порту на всех доступных сетевых интерфейсах
* Кодировка протокола ASCII

Напутствие

К тестовому заданию следует относиться как к упрощенной аналогии настоящего технического задания. Проверяя тестовое задание, рецензент оценивает не только подход к решению, но и критерии качества самого Кандидата.
То есть результатом выполнения тестового задания должно быть идеально написанное с точки зрения Кандидата решение, готовое для production. Протестированное, удовлетворяющее исходному техническому заданию, имеющее максимально аккуратный и чистый код (для простой дальнейшей поддержки).
Не следует посылать задание, которое работает дольше 10 секунд или завершается ошибкой при запуске на тестовом файле test.in. Рецензент будет рассматривать это как невнимательность и халатность при подготовке задания к отправке на проверку, что значительно уменьшает шансы Кандидата.

[OtherSide]

Данная задача состоит из двух частей: базовой и дополнительной. Базовая часть обязательна к решению. Дополнительная является факультативной, но, будучи решенной, может выгодно подчеркнуть знания Кандидата.

Базовая задача

Японцы бесконечно влюблены в технику, которая их окружает. Они внимательно следят за всеми техническими новинками и стараются пользоваться самыми современными и «умными» из них. У Дена и Сергея есть гениальный план: они хотят создать текстовый редактор, который покорит японцев. Важнейшей уберинтеллектуальной функцией редактора должна стать функция автодополнения. Если пользователь набрал несколько первых букв слова, редактор должен предложить ему самые правдоподобные окончания.
Ден и Сергей уже собрали огромное количество японских текстов. Для каждого слова японского языка они посчитали число раз, которое оно встречается в текстах. Если пользователь уже ввел несколько букв, то редактор должен показать не более десяти самых часто употребляемых слов, начинающихся со введенных пользователем букв, отсортированных по убыванию частоты упоминания.
Помогите Сергею с Деном перевернуть рынок текстовых редакторов.
Исходные данные
В первой строке находится единственное число N (1 ≤ N ≤ 105) — количество слов в найденных текстах. Каждая из следующих N строк содержит слово wi (непустая последовательность строчных латинских букв длиной не более 15) и целое число ni (1 ≤ ni ≤ 106) — число раз, которое встречается это слово в текстах. Слово и число разделены единственным пробелом. Ни одно слово не повторяется более одного раза. В (N + 2)-й строке находится число M (1 ≤ M ≤ 15000). В следующих M строках содержатся слова ui (непустая последовательность строчных латинских букв длиной не более 15) — начала слов, введенных пользователем.
Результат
Для каждой из M строк необходимо вывести наиболее часто употребляемые японские слова, начинающихся с ui, в порядке убывания частоты. В случае совпадения частот слова необходимо сортировать по алфавиту. Если существует больше десяти возможных вариантов, то вывести нужно лишь первые десять из них. Варианты дополнения для каждого слова необходимо разделять переводами строк.
Пример
исходные данные результат
5
kare 10
kanojo 20
karetachi 1
korosu 7
sakura 3
3
k
ka
kar kanojo
kare
korosu
karetachi

kanojo
kare
karetachi

kare
karetachi


Решение должно отвечать следующим требованиям:
• Программа должна являться консольным приложением.
• Входные данные подаются программе в стандартном потоке ввода (ввод с клавиатуры). Программа должна выводить ответ в стандартный поток вывода (вывод на экран).
• Программа должна выводить только те данные, которые требует условие задачи. Выводить приглашение для ввода («Введите N:») не нужно. Также не нужно ожидать нажатия клавиши в конце работы программы.
• Solution для VS 11, 2010 или 2008
• Код на C# в стиле, соответствующем рекомендациям http://msdn.microsoft.com/en-us/library/ms229042.aspx
• Решение должно работать быстро (не больше 1-10 секунд) на тестовом файле test.in, прилагающемся к заданию.
Дополнение
Преобразовать консольное приложение из базовой задачи в сетевой сервис и реализовать клиента для него.

Сервис обрабатывает команды вида "get <prefix>". В ответ на которые отправляет клиенту наиболее часто употребляемые слова из словаря, начинающиеся с <prefix>, в порядке убывания частоты. В случае совпадения частот слова необходимо сортировать по алфавиту. Варианты дополнения для каждого слова необходимо разделять переводами строк.

В серверном приложении реализовать поддержку нескольких одновременных клиентских соединений с эффективной многопоточностью. Эффективность измеряется значением throughput.
Ограничения на использование серверных ресурсов отсутствуют.
Сервер
Сервер — это консольное приложение, которое при старте принимает в качестве параметра
путь к текстовому файлу, содержащему словарь, и номер порта.

Клиент
Консольное приложение.
При старте принимает в качестве параметров командной строки IP адрес или hostname, а также порт сервера.

Общие требования к организации сетевого обмена
* TCP/IP v4
* Сервер должен обслуживать все соединения по заданному порту на всех доступных сетевых интерфейсах
* Кодировка протокола ASCII

Напутствие

К тестовому заданию следует относиться как к упрощенной аналогии настоящего технического задания. Проверяя тестовое задание, рецензент оценивает не только подход к решению, но и критерии качества самого Кандидата.
То есть результатом выполнения тестового задания должно быть идеально написанное с точки зрения Кандидата решение, готовое для production. Протестированное, удовлетворяющее исходному техническому заданию, имеющее максимально аккуратный и чистый код (для простой дальнейшей поддержки).
Не следует посылать задание, которое работает дольше 10 секунд или завершается ошибкой при запуске на тестовом файле test.in. Рецензент будет рассматривать это как невнимательность и халатность при подготовке задания к отправке на проверку, что значительно уменьшает шансы Кандидата.

[Pantigalt]

Вам надо в лексикографическом порядке отсортировать словарь.
В нем бинарным поиском искать начало интервала (префикс) и конец интервала (следующая за префиксом последовательность с таким же количеством символов, аналог в С++ next_permutation).
И из этого интервала взять последовательно 10 (или меньше) окончаний слов.
Тут сравнение надо делать лексикографически.

[OtherSide]

они так словарь составили, что между началом и концом несколько сотен окончаний, что бы взять 10, нужно эти несколько сотен отсортировать каждый раз.
Думаю, кеширование тут правильное решение

[АццкоМото]

Вам надо в лексикографическом порядке отсортировать словарь.
В нем бинарным поиском искать начало интервала (префикс) и конец интервала (следующая за префиксом последовательность с таким же количеством символов, аналог в С++ next_permutation).
И из этого интервала взять последовательно 10 (или меньше) окончаний слов.
Тут сравнение надо делать лексикографически.

Интервал только еще нужно отсортировать по частоте (и алфавиту при равенстве частоты); как вариант - частичная сортировка, она быстрее, особенно если нам нужен только топ-10
Из-за этого дополнения сложность улетает с O(log n) до O(n)

[АццкоМото]

ЗЫ. А у OtherSide вышло n*log(n) - от чего все и сломалось

[OtherSide]

Как понять - отсортировать еще? Мы или по алфавиту сортируем, или по весу. Я использовал дерево. Легко и быстро мы можем получить доступ к ветке, которая хранит все окончания. Но как я понял, без полного обхода веток мы не получим полностью надежный результат. Можно, например, в каждом узле хранить максиальное значение из всех ветвей - но нам нужно не одно значение, а 10

[OtherSide]

почему это у меня сложность n*log(n)?

скорее o(log(n)) + o(m) , где m - длина промежутка. Причем логарифм по основанию 26, а не 2

[Pantigalt]

Как понять - отсортировать еще? Мы или по алфавиту сортируем, или по весу. Я использовал дерево. Легко и быстро мы можем получить доступ к ветке, которая хранит все окончания. Но как я понял, без полного обхода веток мы не получим полностью надежный результат. Можно, например, в каждом узле хранить максиальное значение из всех ветвей - но нам нужно не одно значение, а 10

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

[OtherSide]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Japan
{
public class WordPairComparer : IComparer<WordPair>
{
public int Compare(WordPair x, WordPair y)
{
return y.Weight - x.Weight;
}
}

public class WordPair
{
string m_word;
int m_weight;

public string Word { get { return m_word; } }
public int Weight { get { return m_weight; } }

public WordPair(string _word, int _weight)
{
m_word = _word;
m_weight = _weight;
}
}

class CharNode
{
#region const

const int HINT_DEEP = 10;

#endregion

#region private

char m_Letter;
WordPair m_WordPair = null;
Dictionary<char, CharNode> m_Dictionary = new Dictionary<char, CharNode>();

CharNode GetOrCreateNextChar(char c)
{
if (m_Dictionary.ContainsKey(c))
return m_Dictionary[c];

m_Dictionary[c] = new CharNode(c);
return m_Dictionary[c];
}

CharNode NodeFromString(string _Word)
{
CharNode root = this;
foreach (char c in _Word.ToCharArray())
{
if (root.m_Dictionary.ContainsKey(c))
root = root.m_Dictionary[c];
else
return null;
}
return root;
}

void ListFromNode(List<WordPair> _Outlist)
{
foreach (KeyValuePair<char, CharNode> key in m_Dictionary)
{
if (key.Value.m_WordPair != null)
AddToListLimit(_Outlist, key.Value.m_WordPair, HINT_DEEP);

if (key.Value.m_Dictionary.Count > 0)
key.Value.ListFromNode(_Outlist);
}
}

void AddToListLimit(List<WordPair> _List, WordPair _Value, int _Limit)
{
int c = _List.Count;

if (c < _Limit)
_List.Add(_Value);
else
{
int index = 0;

for (int i = 0; i < c; i++)
if (_List.Weight < _List[index].Weight)
index = i;

if (_Value.Weight > _List[index].Weight)
_List[index] = _Value;
}
}

#endregion

#region public

public CharNode(char c)
{
m_Letter = c;
}

public void AddWord(string _Word, int _Weight)
{
CharNode root = this;

foreach (char c in _Word.ToCharArray())
root = root.GetOrCreateNextChar(c);

root.m_WordPair = new WordPair(_Word, _Weight);
}

public List<WordPair> ListFromWord(string _Word)
{
CharNode node = NodeFromString(_Word);
if (node == null)
return null;

List<WordPair> list = new List<WordPair>();
node.ListFromNode(list);

list.Sort(new WordPairComparer());
return list;
}

#endregion
}

class Program
{
static void Main(string[] args)
{
CharNode root_node = new CharNode(' ');

using (System.IO.TextReader readFile = new StreamReader(Console.OpenStandardInput()))
{
int lines = int.Parse(readFile.ReadLine());
for (int i = 0; i < lines; i++)
{
string[] line = readFile.ReadLine().Split(' ');
root_node.AddWord(line[0], int.Parse(line[1]));
}

lines = int.Parse(readFile.ReadLine());
var cacher = new Dictionary<string, List<WordPair>>();

for (int i = 0; i < lines; i++)
{
string line = readFile.ReadLine();
List<WordPair> list;

if (cacher.ContainsKey(line))
list = cacher[line];
else
{
list = root_node.ListFromWord(line);
if (line.Length < 5)
cacher[line] = list;
}

if (list != null)
{
foreach (WordPair pair in list)
Console.WriteLine(pair.Word);
}

Console.WriteLine();
}
}
}
}
}

[Pantigalt]

public List<WordPair> ListFromWord(string _Word)
{
CharNode node = NodeFromString(_Word);
if (node == null)
return null;

List<WordPair> list = new List<WordPair>();
node.ListFromNode(list);

list.Sort(new WordPairComparer());
return list;
}

Вы когда делаете list.Sort то какой алгоритм тут используется?
Предполагаю что быстрая сортировка N*log(N) или в случае малых N - сортировка вставками.
Вместо частичной сортировки у вас получается полная.

[Pantigalt]

В наихудшем случае вам придется искать по всем словам. В вашей реализации - по всему дереву.

[АццкоМото]

почему это у меня сложность n*log(n)?

скорее o(log(n)) + o(m) , где m - длина промежутка. Причем логарифм по основанию 26, а не 2

потому что "нужно эти несколько сотен отсортировать каждый раз."
потом вдруг дерево получилось. запутался я в ваших показаниях.
а, да. основание логарифма - уаще не важно

[АццкоМото]

А вообще нужно заранее дерево построить, где у каждого нода хранится топ-10 окончаний и имеется 0..26 деток. О(1)

[OtherSide]

Вы когда делаете list.Sort то какой алгоритм тут используется?
Предполагаю что быстрая сортировка N*log(N) или в случае малых N - сортировка вставками.
Вместо частичной сортировки у вас получается полная.

Это я уже результат сортирую

[OtherSide]

А вообще нужно заранее дерево построить, где у каждого нода хранится топ-10 окончаний и имеется 0..26 деток. О(1)

Время построения дерева включено в эти 10 секунд. Ну и по сути это тоже кеширование будет.

[OtherSide]

Ладно, обсуждать тут нечего уже. Кеширование снизило результат с 17 секунд до 0.3 секунды на их тестовом наборе. Причем словарь получился всего около 300 пар. думаю этого достаточно

[Berlaga]

Ден и Сергей уже собрали огромное количество японских текстов. Для каждого слова японского языка они посчитали число раз, которое оно встречается в текстах. Если пользователь уже ввел несколько букв, то редактор должен показать не более десяти самых часто употребляемых слов, начинающихся со введенных пользователем букв, отсортированных по убыванию частоты упоминания.
Помогите Сергею с Деном перевернуть рынок текстовых редакторов.
Исходные данные
В первой строке находится единственное число N (1 ≤ N ≤ 105) — количество слов в найденных текстах. Каждая из следующих N строк содержит слово wi (непустая последовательность строчных латинских букв длиной не более 15) и целое число ni (1 ≤ ni ≤ 106) — число раз, которое встречается это слово в текстах. Слово и число разделены единственным пробелом. Ни одно слово не повторяется более одного раза. В (N + 2)-й строке находится число M (1 ≤ M ≤ 15000). В следующих M строках содержатся слова ui (непустая последовательность строчных латинских букв длиной не более 15) — начала слов, введенных пользователем.
Результат
Для каждой из M строк необходимо вывести наиболее часто употребляемые японские слова, начинающихся с ui, в порядке убывания частоты. В случае совпадения частот слова необходимо сортировать по алфавиту. Если существует больше десяти возможных вариантов, то вывести нужно лишь первые десять из них. Варианты дополнения для каждого слова необходимо разделять переводами строк.

Имеем N <= 105 слов, каждое длиной не более 15 букв. Частота не более 106. Построим словарь, ключами в котором будут все возможные префиксы из исходного набора, а значением - слова.

Для получения кличей разобьем каждое слово на <=15 слов следующим образом.
Допустим наша строка
kanojo 20 (заметим, что 106 - 20 = 86, это код символа дополнения, чтобы сортировать было удобно, см. ниже)
karetachi 1 (106 - 1 = 105)
...
Итоговый словарь:
k86 -> kanojo
ka86 -> kanojo
kan86 -> kanojo
kano86 -> kanojo
kanoj86 -> kanojo
kanojo86 -> kanojo

k105 -> karetachi
ka105 -> karetachi
kar105 -> karetachi
kare105 -> karetachi
karet105 -> karetachi
kareta105 -> karetachi
karetac105 -> karetachi
karetach105 -> karetachi
karetachi105 -> karetachi

...

В результате для всего входного набора получим не более 105 * 15 ~= 1500 строк для нового словаря. Этот новый словаряь нужно отсортироватьпо ключам и дальше тупо поиском по нему находить совпадение с префиксом, читать словарь и выбирать 10 (или сколько есть) значений. Для приведенный данных будет
k:
k86 -> kanojo
k96 -> kare
k99 -> korosu
k105 -> karetachi

ka:
ka86 -> kanojo
ka96 -> kare
ka105 -> karetachi
...

Т.е., все сортировки происходят 1 раз, а для каждого ui нужно просто сделать 1 поиск и 10 чтений. Ничего дополнительно сортировать не надо.

[OtherSide]

Я даже как-то не заметил про 105. Однако в файле, что дали стоит 100000

[Berlaga]

А, там наверное 10^5 ! А я еще удивился почему такая точность.