Разбор одного терабайта текста и эффективное подсчет количества вхождений каждого слова

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

  1. Прочтите 1 терабайт контента
  2. Сделать счет для каждого повторного слова в этом содержании
  3. Список 10 самых популярных слов

Не могли бы вы сообщить мне наилучший способ создания алгоритма для этого?

Редактировать:

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

Интервью

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

  1. Разделить входные данные в словах, используя пробел и пунктуацию как разделители
  2. Подавайте каждое слово, найденное в структуру Trie , при этом счетчик обновляется в узлах, представляющих последнюю букву слова
  3. Пройдите полностью заполненное дерево, чтобы найти узлы с наивысшим значением

В контексте интервью … Я бы продемонстрировал идею Три , рисуя дерево на доске или бумаге. Начните с пустого, затем постройте дерево на основе одного предложения, содержащего хотя бы одно повторяющееся слово. Скажем, «кошка может поймать мышь» . Наконец, покажите, как дерево можно пройти, чтобы найти наивысшие значения. Затем я бы обосновал, как это дерево обеспечивает хорошее использование памяти, хорошую скорость поиска слов (особенно в случае естественного языка, для которого многие слова происходят друг от друга), и подходит для параллельной обработки.

Нарисовать на доске

Нарисуйте пример trie

демонстрация

Программа C # ниже проходит через 2 ГБ текста в 75 сек. На 4-ядерном xeon W3520, максимизируя 8 streamов. Производительность составляет около 4,3 миллиона слов в секунду с менее оптимальным кодом синтаксического ввода. С помощью структуры Trie для хранения слов память не является проблемой при обработке ввода естественного языка.

Заметки:

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

using System; using System.Collections.Generic; using System.Collections.Concurrent; using System.IO; using System.Threading; namespace WordCount { class MainClass { public static void Main(string[] args) { Console.WriteLine("Counting words..."); DateTime start_at = DateTime.Now; TrieNode root = new TrieNode(null, '?'); Dictionary readers = new Dictionary(); if (args.Length == 0) { args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt", "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" }; } if (args.Length > 0) { foreach (string path in args) { DataReader new_reader = new DataReader(path, ref root); Thread new_thread = new Thread(new_reader.ThreadRun); readers.Add(new_reader, new_thread); new_thread.Start(); } } foreach (Thread t in readers.Values) t.Join(); DateTime stop_at = DateTime.Now; Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds); Console.WriteLine(); Console.WriteLine("Most commonly found words:"); List top10_nodes = new List { root, root, root, root, root, root, root, root, root, root }; int distinct_word_count = 0; int total_word_count = 0; root.GetTopCounts(ref top10_nodes, ref distinct_word_count, ref total_word_count); top10_nodes.Reverse(); foreach (TrieNode node in top10_nodes) { Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count); } Console.WriteLine(); Console.WriteLine("{0} words counted", total_word_count); Console.WriteLine("{0} distinct words found", distinct_word_count); Console.WriteLine(); Console.WriteLine("done."); } } #region Input data reader public class DataReader { static int LOOP_COUNT = 1; private TrieNode m_root; private string m_path; public DataReader(string path, ref TrieNode root) { m_root = root; m_path = path; } public void ThreadRun() { for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times { using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read)) { using (StreamReader sreader = new StreamReader(fstream)) { string line; while ((line = sreader.ReadLine()) != null) { string[] chunks = line.Split(null); foreach (string chunk in chunks) { m_root.AddWord(chunk.Trim()); } } } } } } } #endregion #region TRIE implementation public class TrieNode : IComparable { private char m_char; public int m_word_count; private TrieNode m_parent = null; private ConcurrentDictionary m_children = null; public TrieNode(TrieNode parent, char c) { m_char = c; m_word_count = 0; m_parent = parent; m_children = new ConcurrentDictionary(); } public void AddWord(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right? { if (!m_children.ContainsKey(key)) { m_children.TryAdd(key, new TrieNode(this, key)); } m_children[key].AddWord(word, index + 1); } else { // not a letter! retry with next char AddWord(word, index + 1); } } else { if (m_parent != null) // empty words should never be counted { lock (this) { m_word_count++; } } } } public int GetCount(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (!m_children.ContainsKey(key)) { return -1; } return m_children[key].GetCount(word, index + 1); } else { return m_word_count; } } public void GetTopCounts(ref List most_counted, ref int distinct_word_count, ref int total_word_count) { if (m_word_count > 0) { distinct_word_count++; total_word_count += m_word_count; } if (m_word_count > most_counted[0].m_word_count) { most_counted[0] = this; most_counted.Sort(); } foreach (char key in m_children.Keys) { m_children[key].GetTopCounts(ref most_counted, ref distinct_word_count, ref total_word_count); } } public override string ToString() { if (m_parent == null) return ""; else return m_parent.ToString() + m_char; } public int CompareTo(TrieNode other) { return this.m_word_count.CompareTo(other.m_word_count); } } #endregion } 

Здесь результат обработки одного и того же 20 МБ текста 100 раз по 8 streamам.

 Counting words... Input data processed in 75.2879952 secs Most commonly found words: the - 19364400 times of - 10629600 times and - 10057400 times to - 8121200 times a - 6673600 times in - 5539000 times he - 4113600 times that - 3998000 times was - 3715400 times his - 3623200 times 323618000 words counted 60896 distinct words found 

Здесь многое зависит от некоторых вещей, которые не были указаны. Например, пытаемся ли мы сделать это один раз , или мы пытаемся создать систему, которая будет делать это на регулярной и постоянной основе? У нас есть какой-то контроль над вводом? Имеем ли мы дело с текстом, который находится на одном языке (например, на английском языке) или на многих языках представлен (и если да, то сколько)?

Это связано с тем, что:

  1. Если данные начинаются на одном жестком диске, параллельный подсчет (например, уменьшение карты) не будет делать ничего хорошего – узким местом будет скорость передачи с диска. Создание копий на большее количество дисков, чтобы мы могли рассчитывать быстрее, будет медленнее, чем просто подсчет непосредственно с одного диска.
  2. Если мы разрабатываем систему для этого на регулярной основе, большая часть нашего акцента на самом деле заключается в аппаратном обеспечении – в частности, есть много дисков параллельно, чтобы увеличить пропускную способность и, по крайней мере, немного приблизиться к тому, чтобы идти в ногу с ЦПУ.
  3. Независимо от того, сколько текста вы читаете, существует ограничение на количество дискретных слов, с которыми вам нужно иметь дело – есть ли у вас терабайт даже петабайта английского текста, вы не увидите ничего, как миллиарды разные слова на английском языке. Выполняя быструю проверку, Оксфордский английский словарь содержит около 600 000 слов на английском языке.
  4. Хотя фактические слова, очевидно, различны между языками, количество слов на одном языке является примерно постоянным, поэтому размер построенной нами карты будет в значительной степени зависеть от количества представленных языков.

Это в основном оставляет вопрос о том, сколько языков может быть представлено. На данный момент допустим худший случай. ISO 639-2 имеет коды для 485 человеческих языков. Предположим, что в среднем 700 000 слов на язык и средняя длина слова, скажем, 10 байт UTF-8 за слово.

Просто хранится как простой линейный список, это означает, что мы можем хранить каждое слово на каждом языке на земле вместе с 8-байтным числом частот в немногим менее 6 гигабайт. Если мы вместо этого используем что-то вроде Patricia trie, возможно , мы планируем сократить это, по крайней мере, несколько – возможно, до 3 гигабайт или меньше, хотя я не знаю достаточно обо всех этих языках, чтобы быть уверенным.

Теперь реальность такова, что мы почти наверняка переоценили числа в ряде мест – на нескольких языках имеется множество слов, многие (особенно старые) языки, вероятно, имеют меньше слов, чем английский, и просматривают список, похоже, некоторые из них включены, что, вероятно, вообще не имеют письменных форм.

Резюме. Почти любой разумно новый рабочий стол / сервер имеет достаточно памяти для полного хранения карты в ОЗУ – и больше данных это не изменит. Для одного (или нескольких) дисков параллельно, мы все равно будем привязаны к вводу / выводу, поэтому параллельный подсчет (и такой), вероятно, будет чистым убытком. Нам, вероятно, нужно несколько десятков дисков параллельно, прежде чем какая-либо другая оптимизация потребует многого.

Для этой задачи вы можете попробовать подход, уменьшающий карту . Преимуществом map-reduce является масштабируемость, поэтому даже для 1 ТБ, или 10 ТБ или 1 ПБ – тот же подход будет работать, и вам не нужно будет много работать, чтобы изменить свой алгоритм для нового масштаба. Рамка также позаботится о распределении работы между всеми машинами (и ядрами), которые у вас есть в вашем кластере.

Сначала создайте пары (word,occurances) .
Псевдокод для этого будет примерно таким:

 map(document): for each word w: EmitIntermediate(w,"1") reduce(word,list): Emit(word,size(list)) 

Во-вторых, вы можете легко найти те, которые имеют самые высокие вершины topK, с одной итерацией по парам. Эта тема объясняет эту концепцию. Основная идея состоит в том, чтобы удерживать мини-кучу верхних элементов K, а при повторении – убедитесь, что куча всегда содержит верхние K-элементы, которые были обнаружены до сих пор. Когда вы закончите – куча содержит верхние элементы K.

Более масштабируемая (хотя и медленная, если у вас мало машин) альтернатива – вы используете функцию сортировки с уменьшением карты и сортируете данные в соответствии с событиями, а только grep top K.

Три примечательных момента для этого.

В частности: файл для большого хранения в памяти, список слов (потенциально) слишком большой для хранения в памяти, количество слов может быть слишком большим для 32-битного int.

Как только вы пройдете эти предостережения, это должно быть прямо. Игра управляет потенциально большим списком слов.

Если это будет легче (держать голову от вращения).

«У вас работает 8-битная машина Z-80 с 65 КБ оперативной памяти и 1 МБ-файл …»

То же точно проблема.

Это зависит от требований, но если вы можете позволить себе некоторую ошибку, streamовые алгоритмы и вероятностные структуры данных могут быть интересными, поскольку они очень эффективны во времени и пространстве и довольно просты в реализации, например:

  • Тяжелые нападающие (например, Space Saving), если вас интересуют только самые популярные слова
  • Граф-мин-эскиз, чтобы получить расчетный счет для любого слова

Эти структуры данных требуют лишь очень небольшого постоянного пространства (точное количество зависит от ошибки, которую вы можете терпеть).

См. http://alex.smola.org/teaching/berkeley2012/streams.html для отличного описания этих алгоритмов.

Мне было бы очень сложно использовать DAWG ( wikipedia и C # writeup с более подробной информацией ). Это достаточно просто, чтобы добавить поле счетчика на листовых узлах, эффективно использовать память и очень хорошо подходит для поиска.

EDIT: Хотя вы пробовали просто использовать Dictionary ? Где > обозначает слово и число? Возможно, вы пытаетесь оптимизировать слишком рано?

Примечание редактора: это сообщение, первоначально связанное с этой статьей wikipedia , которая, по-видимому, касается другого значения термина DAWG: способ хранения всех подстрок одного слова для эффективного приближенного сопоставления строк.

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

Затем используйте запрос (извините за проблему синтаксиса, мой SQL ржавый – это псевдокод):

 SELECT DISTINCT word, COUNT(*) AS c FROM myTable GROUP BY word ORDER BY c DESC 

Общая идея состоит в том, чтобы сначала создать таблицу (которая хранится на диске) со всеми словами, а затем использовать запрос для подсчета и сортировки (word,occurances) для вас. Затем вы можете просто взять верхний K из извлеченного списка.


Для всех: Если у меня действительно есть синтаксис или другие проблемы в инструкции SQL: не стесняйтесь редактировать

Во-первых, я только недавно «обнаружил» структуру данных Trie, и ответ zeFrenchy был отличным для того, чтобы ускорить его.

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

Я хотел бы поиграть с локальным хранилищем streamов, и ваш образец дал мне отличную возможность сделать это и после некоторых незначительных изменений использовать словарь для streamа, а затем объединить словари после того, как Join () увидела, что производительность улучшилась на 30% (обработка 20 Мбайт 100 раз по 8 нитям менялась от ~ 48 сек до ~ 33 с на моем ящике).

Код будет вставлен ниже, и вы заметите, что он не сильно изменился с утвержденного ответа.

PS У меня не более 50 очков репутации, поэтому я не мог поместить это в комментарий.

 using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Threading; namespace WordCount { class MainClass { public static void Main(string[] args) { Console.WriteLine("Counting words..."); DateTime start_at = DateTime.Now; Dictionary readers = new Dictionary(); if (args.Length == 0) { args = new string[] { "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt", "war-and-peace.txt", "ulysees.txt", "les-miserables.txt", "the-republic.txt" }; } List> roots; if (args.Length == 0) { roots = new List>(1); } else { roots = new List>(args.Length); foreach (string path in args) { ThreadLocal root = new ThreadLocal(() => { return new TrieNode(null, '?'); }); roots.Add(root); DataReader new_reader = new DataReader(path, root); Thread new_thread = new Thread(new_reader.ThreadRun); readers.Add(new_reader, new_thread); new_thread.Start(); } } foreach (Thread t in readers.Values) t.Join(); foreach(ThreadLocal root in roots.Skip(1)) { roots[0].Value.CombineNode(root.Value); root.Dispose(); } DateTime stop_at = DateTime.Now; Console.WriteLine("Input data processed in {0} secs", new TimeSpan(stop_at.Ticks - start_at.Ticks).TotalSeconds); Console.WriteLine(); Console.WriteLine("Most commonly found words:"); List top10_nodes = new List { roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value, roots[0].Value }; int distinct_word_count = 0; int total_word_count = 0; roots[0].Value.GetTopCounts(top10_nodes, ref distinct_word_count, ref total_word_count); top10_nodes.Reverse(); foreach (TrieNode node in top10_nodes) { Console.WriteLine("{0} - {1} times", node.ToString(), node.m_word_count); } roots[0].Dispose(); Console.WriteLine(); Console.WriteLine("{0} words counted", total_word_count); Console.WriteLine("{0} distinct words found", distinct_word_count); Console.WriteLine(); Console.WriteLine("done."); Console.ReadLine(); } } #region Input data reader public class DataReader { static int LOOP_COUNT = 100; private TrieNode m_root; private string m_path; public DataReader(string path, ThreadLocal root) { m_root = root.Value; m_path = path; } public void ThreadRun() { for (int i = 0; i < LOOP_COUNT; i++) // fake large data set buy parsing smaller file multiple times { using (FileStream fstream = new FileStream(m_path, FileMode.Open, FileAccess.Read)) using (StreamReader sreader = new StreamReader(fstream)) { string line; while ((line = sreader.ReadLine()) != null) { string[] chunks = line.Split(null); foreach (string chunk in chunks) { m_root.AddWord(chunk.Trim()); } } } } } } #endregion #region TRIE implementation public class TrieNode : IComparable { private char m_char; public int m_word_count; private TrieNode m_parent = null; private Dictionary m_children = null; public TrieNode(TrieNode parent, char c) { m_char = c; m_word_count = 0; m_parent = parent; m_children = new Dictionary(); } public void CombineNode(TrieNode from) { foreach(KeyValuePair fromChild in from.m_children) { char keyChar = fromChild.Key; if (!m_children.ContainsKey(keyChar)) { m_children.Add(keyChar, new TrieNode(this, keyChar)); } m_children[keyChar].m_word_count += fromChild.Value.m_word_count; m_children[keyChar].CombineNode(fromChild.Value); } } public void AddWord(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (char.IsLetter(key)) // should do that during parsing but we're just playing here! right? { if (!m_children.ContainsKey(key)) { m_children.Add(key, new TrieNode(this, key)); } m_children[key].AddWord(word, index + 1); } else { // not a letter! retry with next char AddWord(word, index + 1); } } else { if (m_parent != null) // empty words should never be counted { m_word_count++; } } } public int GetCount(string word, int index = 0) { if (index < word.Length) { char key = word[index]; if (!m_children.ContainsKey(key)) { return -1; } return m_children[key].GetCount(word, index + 1); } else { return m_word_count; } } public void GetTopCounts(List most_counted, ref int distinct_word_count, ref int total_word_count) { if (m_word_count > 0) { distinct_word_count++; total_word_count += m_word_count; } if (m_word_count > most_counted[0].m_word_count) { most_counted[0] = this; most_counted.Sort(); } foreach (char key in m_children.Keys) { m_children[key].GetTopCounts(most_counted, ref distinct_word_count, ref total_word_count); } } public override string ToString() { return BuildString(new StringBuilder()).ToString(); } private StringBuilder BuildString(StringBuilder builder) { if (m_parent == null) { return builder; } else { return m_parent.BuildString(builder).Append(m_char); } } public int CompareTo(TrieNode other) { return this.m_word_count.CompareTo(other.m_word_count); } } #endregion } 

В качестве быстрого общего алгоритма я бы сделал это.

 Create a map with entries being the count for a specific word and the key being the actual string. for each string in content: if string is a valid key for the map: increment the value associated with that key else add a new key/value pair to the map with the key being the word and the count being one done 

Тогда вы можете просто найти наибольшее значение на карте

 create an array size 10 with data pairs of (word, count) for each value in the map if current pair has a count larger than the smallest count in the array replace that pair with the current one print all pairs in array 

Ну, лично я разделил бы файл на разные размеры, скажем, 128 Мб, все время сохраняя два в памяти, в то время как scannng, любое обнаруженное слово добавляется в список хешей и список списка, тогда я бы перебирал список списка в конце, чтобы найти лучшие 10 …

Ну, первая мысль состоит в том, чтобы управлять dtabase в форме хеш-таблицы / массива или что-то, что бы сохранить каждое появление слов, но в соответствии с размером данных я бы предпочел:

  • Получите первые 10 найденных слов, где встречаемость> = 2
  • Получите, сколько раз эти слова происходят во всей строке и удаляют их при подсчете
  • Начните снова, как только у вас есть два набора из 10 слов, каждый из которых вы получите самые последние 10 слов обоих наборов
  • Сделайте то же самое для остальной части строки (которая dosnt содержит эти слова больше).

Вы даже можете попытаться быть более эффективным и начать с 1-го найденного 10 слов, где встречаемость> = 5, например, или больше, если не найдена, уменьшите это значение до 10 слов. Throuh это у вас есть хороший шанс избежать использования памяти, интенсивно сохраняя все слова, которые представляют собой огромный объем данных, и вы можете сохранить раунды сканирования (в хорошем случае)

Но в худшем случае у вас может быть больше раундов, чем в обычном алгоритме.

Кстати, это проблема, которую я постараюсь решить с помощью функционального языка программирования, а не ООП.

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

  • Прочтите файл в кусках, скажем, 1 ГБ
  • Для каждого fragmentа сделайте список, скажем, 5000 наиболее встречающихся слов с их частотой
  • Объединение списков на основе частоты (1000 списков по 5000 слов каждый)
  • Верните 10 лучших объединенных списков

Теоретически вы можете пропустить слова, хотя я думаю, что шанс очень маленький.

Шторм – это технология, на которую нужно смотреть. Он отделяет роль ввода данных (носиков) от процессоров (болтов). Глава 2 штормовой книги решает вашу точную проблему и очень хорошо описывает архитектуру системы – http://www.amazon.com/Getting-Started-Storm-Jonathan-Leibiusky/dp/1449324010

Storm – это больше обработки в режиме реального времени, а не пакетной обработки с Hadoop. Если ваши данные соответствуют существующим, вы можете распределять нагрузки на разные носики и распространять их для обработки на разные болты.

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

Очень интересный вопрос. Это больше связано с логическим анализом, чем с кодированием. С предположением английского языка и действительными предложениями это становится проще.

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

Что касается чтения файла, вы должны выбрать параллельный режим, считывая fragmentы (размер по вашему выбору), манипулируя позициями файлов для пробелов. Если вы решили прочитать куски 1 МБ, например, все куски, кроме первого, должны быть немного шире (+22 байта слева и +22 байта справа, где 22 представляет собой самое длинное английское слово – если я прав). Для параллельной обработки вам потребуется параллельный словарь или локальные коллекции, которые вы объедините.

Имейте в виду, что обычно вы попадаете в первую десятку как часть действительного списка стоп-слов (это, вероятно, еще один обратный подход, который также действителен до тех пор, пока содержимое файла является обычным).

Попытайтесь придумать специальную структуру данных для решения таких проблем. В этом случае особый вид дерева вроде trie для хранения строк определенным образом, очень эффективен. Или второй способ создать собственное решение, например, подсчет слов. Я предполагаю, что этот ТБ данных будет на английском языке, тогда у нас будет около 600 000 слов вообще, поэтому можно будет хранить только эти слова и подсчитывать, какие строки будут повторяться + этому решению потребуется регулярное выражение, чтобы устранить некоторые специальные символы. Первое решение будет быстрее, я уверен.

http://en.wikipedia.org/wiki/Trie

вот реализация шины в java
http://algs4.cs.princeton.edu/52trie/TrieST.java.html

Уменьшение карты
WordCount можно эффективно использовать с помощью mapreduce с использованием hadoop. https://hadoop.apache.org/docs/r1.2.1/mapred_tutorial.html#Example%3A+WordCount+v1.0 Большие файлы могут быть проанализированы через него. Он использует несколько узлов в кластере для выполнения этой операции.

 public void map(LongWritable key, Text value, OutputCollector output, Reporter reporter) throws IOException { String line = value.toString(); StringTokenizer tokenizer = new StringTokenizer(line); while (tokenizer.hasMoreTokens()) { word.set(tokenizer.nextToken()); output.collect(word, one); } } public static class Reduce extends MapReduceBase implements Reducer { public void reduce(Text key, Iterator values, OutputCollector output, Reporter reporter) throws IOException { int sum = 0; while (values.hasNext()) { sum += values.next().get(); } output.collect(key, new IntWritable(sum)); } } 
  • Как создать комбинации нескольких векторов без контуров жесткого кодирования в C ++?
  • Края на контурах многоугольника не всегда правильны
  • Сопоставление двух целых чисел с единым, уникальным и детерминированным образом
  • Как восстановить приоритет PriorityQueue до его начального состояния перед вызовом метода?
  • Переупорядочение элементов массива
  • Почему алгоритм Дейкстры не работает для отрицательных границ веса?
  • Алгоритм для поиска чисел из списка размера n sum на другое число
  • Самый элегантный способ генерации простых чисел
  • Магический номер в boost :: hash_combine
  • Постоянное амортизированное время
  • Округление до произвольного количества значащих цифр
  • Давайте будем гением компьютера.