Graeme_Grant
Как и некоторые другие, я использовал таблицу поиска, но с изюминкой. Один Dictionary с помощью специализированного ключа группировки.
Ключ находится в <Tuple<int, long, long> состоит из длины слов и пары оснований 26 Longs. поскольку в английских словах есть 26 символов, я разделил строчный алфавит на половинки - от a до l (от 0 до 12) до нижнего & m до z (от 13 до 26) до верхнего.
То Find метод запускается в миллисекундах, почти мгновенно, со списком из более чем 350 000 слов. Длина слова не влияет на производительность.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using ZeroFormatter;
namespace BuildLookupFile
{
static class Program
{
static void Main(string[] args)
{
Console.WriteLine("Anagram Lookup File Builder");
Console.WriteLine("===========================");
var helper = new AnagramsHelper();
var sw = new Stopwatch();
Console.WriteLine("\r\nLoading & building Lookup Table...");
sw.Start();
helper.LoadWords("words.txt");
var elapsed = sw.Elapsed;
Console.WriteLine("* Loaded & processed in {0:N6} seconds",
elapsed.TotalMilliseconds / 1000);
Console.WriteLine("\r\nStatistics");
Console.WriteLine("----------");
Console.WriteLine("* {0:N0} words", helper.count);
Console.WriteLine("\r\nSaving to file...");
sw.Restart();
helper.SaveTable("words.bin");
elapsed = sw.Elapsed;
Console.WriteLine("* Write to disk took in {0:N6} seconds",
elapsed.TotalMilliseconds / 1000);
}
}
public class AnagramsHelper
{
public int count { get; private set; }
private Dictionary<string, List<string>> LookupTable
= new Dictionary<string, List<string>>();
public void LoadWords(string filename)
{
var wordKeys = new Dictionary<string, int>();
string word, key;
List<string> wordList = null;
using (StreamReader sr = File.OpenText(filename))
{
while ((word = sr.ReadLine()) != null)
{
if (word.Length > 0 && !word.Contains("'") && !word.Contains("\""))
{
key = word.GetKey();
if (!LookupTable.ContainsKey(key))
{
wordList = new List<string>();
LookupTable.Add(key, wordList);
}
else
{
wordList = LookupTable[key];
}
count++;
wordList.Add(word);
}
}
}
}
internal void SaveTable(string filename)
{
using (var fs = File.OpenWrite(filename))
LookupTable.Serialize(fs);
}
}
public static class HelperExtensions
{
public static string GetKey(this string word)
{
var chars = word.ToCharArray();
Array.Sort(chars);
return new string(chars);
}
public static void Serialize(this Dictionary<string, List<string>> data, Stream stream)
{
var writer = new BinaryWriter(stream);
writer.Write(ZeroFormatterSerializer.Serialize(data));
writer.Flush();
}
}
}
Imports System.IO
Imports System.Runtime.CompilerServices
Imports ZeroFormatter
Module Module1
Sub Main()
Console.WriteLine("Anagram Lookup File Builder")
Console.WriteLine("===========================")
Dim helper = New AnagramsHelper()
Dim sw = New Stopwatch()
Console.WriteLine(vbCr & vbLf & "Loading & building Lookup Table...")
sw.Start()
helper.LoadWords("words.txt")
Dim elapsed = sw.Elapsed
Console.WriteLine("* Loaded & processed in {0:N6} seconds", elapsed.TotalMilliseconds / 1000)
Console.WriteLine(vbCr & vbLf & "Statistics")
Console.WriteLine("----------")
Console.WriteLine("* {0:N0} words", helper.count)
Console.WriteLine(vbCr & vbLf & "Saving to file...")
sw.Restart()
helper.SaveTable("words.bin")
elapsed = sw.Elapsed
Console.WriteLine("* Write to disk took in {0:N6} seconds", elapsed.TotalMilliseconds / 1000)
End Sub
End Module
Public Class AnagramsHelper
Public Property count() As Integer
Private LookupTable As New Dictionary(Of String, List(Of String))()
Public Sub LoadWords(filename As String)
Dim word As String
Dim key As String
Dim wordList As List(Of String)
Using sr As StreamReader = File.OpenText(filename)
Do
word = sr.ReadLine()
If word?.Length > 0 AndAlso
Not word.Contains("'") AndAlso
Not word.Contains("""") Then
key = word.GetKey()
If Not LookupTable.ContainsKey(key) Then
wordList = New List(Of String)()
LookupTable.Add(key, wordList)
Else
wordList = LookupTable(key)
End If
count += 1
wordList.Add(word)
End If
Loop While word IsNot Nothing
End Using
End Sub
Friend Sub SaveTable(filename As String)
Using fs = File.OpenWrite(filename)
LookupTable.Serialize(fs)
End Using
End Sub
End Class
Public Module HelperExtensions
<Extension>
Public Function GetKey(word As String) As String
Dim chars = word.ToCharArray()
Array.Sort(chars)
Return New String(chars)
End Function
<Extension>
Public Sub Serialize(data As Dictionary(Of String, List(Of String)), stream As Stream)
Dim writer = New BinaryWriter(stream)
writer.Write(ZeroFormatterSerializer.Serialize(data))
writer.Flush()
End Sub
End Module
И вот каждый выходной:
Ultra-Fast Anagram Generator
============================
Word list supplied by: https://github.com/dwyl/english-words
Loading & building Lookup Table...
Statistics
----------
* 351,096 words
* Loaded & processed in 7.4770 seconds
* Largest group of Anagrams: 15
* Longest word in Lookup Table:
- dichlorodiphenyltrichloroethane
Search Word: teaser
FOUND 9 anagrams for "teaser"
aretes
asteer
easter
eaters
reseat
saeter
seater
staree
teaser
Time: 0.000072 seconds
Search Word: alerts
FOUND 15 anagrams for "alerts"
alerts
alters
artels
estral
laster
lastre
rastle
ratels
relast
resalt
salter
slater
staler
stelar
talers
Time: 0.000072 seconds
ОБНОВЛЕНИЕ: Я обнаружил улучшение производительности за счет упрощения. Положительная сторона заключается в том, что время загрузки улучшается на 300%, А время отклика-более чем на 200%.
Вот пересмотренные результаты:
Ultra-Fast Anagram Generator
============================
Word list supplied by: https://github.com/dwyl/english-words
Loading & building Lookup Table...
Statistics
----------
* 351,096 words
* Loaded & processed in 2.5293 seconds
* Largest group of Anagrams: 15
* Longest word in Lookup Table:
- dichlorodiphenyltrichloroethane
Search Word: teaser
FOUND 9 anagrams for "teaser"
aretes
asteer
easter
eaters
reseat
saeter
seater
staree
teaser
Time: 0.000039 seconds
Search Word: alerts
FOUND 15 anagrams for "alerts"
alerts
alters
artels
estral
laster
lastre
rastle
ratels
relast
resalt
salter
slater
staler
stelar
talers
Time: 0.000034 seconds
Обновление #2.1: Теперь, когда поиск выполняется молниеносно, следующее узкое место производительности, которое необходимо устранить, - это загрузка таблицы поиска. PIEBOLDconsult использует базу данных SQL, поэтому я решил предварительно построить таблицу поиска.
Самым большим узким местом, возникшим при сохранении и загрузке двоичной версии таблицы поиска, была платформа .Net
BinaryFormatter уик потратил более 61 секунды (лучшее время) на десериализацию двоичного потока. Итак, немного поискав, я нашел
ZeroFormatter[
^].
Время загрузки уже наступило уменьшено с 2,5293 секунды до а
молниеносно на 0,534043 секунды - более чем на 500% быстрее и более
1400% быстрее чем оригинал!
Наконец, тоже сжал
бэтэр производительности поиска. Теперь уменьшено с 0,034 МС
до 0,013 МС или улучшение на 261%, и
более чем на 550% быстрее, чем оригинал!
Вот код для построения двоичного файла:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using ZeroFormatter;
namespace BuildLookupFile
{
static class Program
{
static void Main(string[] args)
{
Console.WriteLine("Anagram Lookup File Builder");
Console.WriteLine("===========================");
var helpe
Jörgen Andersson
Действительно ли арест-это анаграмма для тизера?
Арест имеет два R, а тизер-два E.
Graeme_Grant
ха... нужно посмотреть на эту... небольшую заминку...
Graeme_Grant
Обновленный.
Jörgen Andersson
Вероятно, вы можете немного ускорить решение, приняв 32 буквы в алфавите и используя битовый сдвиг.
Graeme_Grant
Спасибо за предложение. Я действительно думал об этом, но мне нужен граф того же письма. Я думаю о другом способе, который, скорее всего, будет и попробую, когда у меня будет время...
Graeme_Grant
На самом деле я покончил с вычисляемым ключом кортежа и перешел на простое использование хэш - кода-гораздо быстрее! теперь до 0,013 МС с 0,074 МС. Но это на моем 4-летнем MBP. Я уверен, что это будет быстрее на более современном ПК... :)
Jörgen Andersson
Это быстрее на более новом компьютере, мой и ваше решение имеет почти такую же скорость на моем компьютере.
Но они должны были иметь, важные части-это почти тот же самый код.
Не только поиск по словарю, но и сравнение вашего GetKey с первой версией моего решения. Он отличается только частью GetHashCode ().
Но я вижу проблему с этой частью вашего нового кода.
Когда вы создаете свой ключ, вы извлекаете хэш-значение из отсортированной строки. В этом нет необходимости, все равно это делается внутри словаря.
Но словарь также имеет встроенную обработку для hashcollisions. Я вообще не вижу никакой обработки хэшколлизий в вашем коде.
GetHashCode является значение типа int32 кстати, так что если вы проходите долго словаре, оно будет вычислять хэш-код как (непроверенные((тип int)((длинные)m_value)) ^ (int)(m_value >> 32)) вместо того, чтобы просто пропустить его, что было бы в случае с Int32.
Graeme_Grant
Мне пришлось удалить код Linq, чтобы повысить производительность. Long-это то, что осталось от предыдущего кода. изменение его на Int32 удалит больше накладных расходов (хотя и очень незначительных) и еще больше сократит использование памяти и хранилища.
Что касается скорости, то сейчас мы проводим измерения, которые нуждаются в другом методе, чтобы получить лучшую точность. ;)
Я действительно проверял хэш-коллизию на основе длины ключа, но ничего не увидел. Итак, для этого упражнения, я чувствовал, что это не было проблемой. Я тоже не видел ничего подобного на случайных проверках ключевых слов.
[edit] нашел, где можно было бы сделать еще один выигрыш perf, и теперь он снизился до 0,0011 МС на моем старом MBP. ;)
Рейтинг:
0
Midi_Mick
Прежде всего, я использую Алгоритм кучи[^] чтобы сгенерировать все возможные перестановки введенных случайных букв, и я помещаю эти перестановки в хэш-набор.
Затем, вместо того чтобы проверять каждую перестановку, чтобы увидеть, является ли это словом, я решил, что словарь все равно должен быть загружен, так почему бы не проверить, подходит ли загружаемое слово? Таким образом, я вообще не загружаю словарь в память - я просто повторяю слова в словаре, которые находятся в списке перестановок. Я использовал то же самое words.txt откуда GitHub - dwyl/english-words: текстовый файл, содержащий 479 тысяч английских слов для быстрого поиска автозавершения / самовнушения.[^] используется в решении 2 для моего словаря.
class Program {
static HashSet<string> _permutations = new HashSet<string>();
static void GeneratePermutations(int n, char[] letters) {
if (n == 1)
_permutations.Add(new string(letters));
else {
for (int i = 0; i < n - 1; ++i) {
GeneratePermutations(n - 1, letters);
int swapIndex = (n & 1) == 0 ? i : 0;
char c = letters[swapIndex];
letters[swapIndex] = letters[n - 1];
letters[n - 1] = c;
}
GeneratePermutations(n - 1, letters);
}
}
static void ListPermutations() {
Console.WriteLine("\nAll Permutations:");
foreach (string permutation in _permutations)
Console.WriteLine(permutation);
}
static void FindWords() {
Console.WriteLine("\nWords:");
using (StreamReader fp = File.OpenText(Path.Combine(Path.GetDirectoryName(Assembly.GetEntryAssembly().Location), "words.txt"))) {
string word;
while ((word = fp.ReadLine()) != null) {
if (_permutations.Contains(word)) {
Console.WriteLine(word);
}
}
}
}
static void Main(string[] args) {
string letters = null;
if ((args?.Length ?? 0) > 0)
letters = args[0];
char action;
do {
while (string.IsNullOrEmpty(letters)) {
Console.Write("Enter random letters: ");
letters = Console.ReadLine().ToLower();
if (letters.Any(c => !char.IsLetter(c)))
letters = null;
}
_permutations.Clear();
GeneratePermutations(letters.Length, letters.ToCharArray());
do {
Console.WriteLine("1. List all permutations");
Console.WriteLine("2. Find Words");
Console.WriteLine("3. Restart");
Console.WriteLine("0. Exit");
action = Console.ReadKey(false).KeyChar;
if (action == '1')
ListPermutations();
else if (action == '2')
FindWords();
} while (action != '3' && action != '0');
letters = null;
} while (action != '0');
}
}
PIEBALDconsult
С помощью хэш-набора вы теряете счет тому, сколько у вас букв, не так ли?
Midi_Mick
Нет = хэш-набор содержит все возможные перестановки, но только по одному разу каждая - он удаляет дубликаты, вызванные удвоением букв. Например, если ввести 5 различных символов, то получится 120 перестановок. Однако если 2 из этих букв одинаковы, то из 120 фактических перестановок различны только 60 - каждая последовательность букв будет сгенерирована дважды (один раз для Буквы в 1-й позиции и один раз для буквы во 2-й позиции). Хэш-набор удаляет эти дубликаты.
PIEBALDconsult
Ах да, мой мозг устал.