词典WinRTMonoXamarinASP.NET Core.NET4.5Visual Studio 2013WebFormsLINQ.NET4高级Windows FormsWPF中级开发.NETVisual BasicASP.NETC#
高速生成字谜
4.90/5 (8投票s)
一篇关于为每周编程挑战寻找最快生成有效字谜的解决方案的记录性旅程……
引言
- 给定一个随机（或不那么随机）的字符串，生成唯一的字谜
- 连接到您选择的拼写检查服务，并且只返回实际是单词的字谜
- 需要是一个快速的解决方案
本文的目的是带您踏上为每周挑战找到最终解决方案所经历的旅程和发现。
该解决方案将是一个控制台应用程序，但代码可以应用于任何其他类型的应用程序 - WinForm、WPF、UWP、Xamarin Native/Forms、ASP.NET、MVC 和 ASP.Core。
免责声明：我不声称这是最好或最快的解决方案，但我认为它已经非常接近了。在发布本文时，挑战尚未结束，所以可能有人找到了更快的解决方案。
简而言之
什么是字谜？
首先，我们需要查看字谜的定义。根据牛津词典[^]：“通过重排另一个词、短语或名称的字母而形成的词、短语或名称，例如“spar”由“rasp”形成。”
1. 构建字谜列表
要生成字谜，您需要找到所有字母的组合。有很多方法可以做到这一点。这是一种方法
static class Program
{
private static object elapsed;
private static void Main(string[] args)
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
var prime = "a".Anagrams();
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Start();
var anagrams = lookupWord.Anagrams();
elapsed = st.Elapsed;
st.Stop();
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
Console.WriteLine($"Time: {elapsed.TotalMilliseconds} ms");
}
}
// derived from http://stackoverflow.com/a/7187466
static IEnumerable<string> Anagrams(this string word)
=> Combinations(word.ToCharArray().ToList())
.Select(x => new string(x.ToArray())).Distinct();
static IEnumerable<list<char>> Combinations(List<char> items)
{
if (items.Count == 0) yield return new List<char>();
var copy = new List<char>(items);
foreach (var i in items)
{
copy.Remove(i);
foreach (var rest in Combinations(copy))
{
rest.Insert(0, i);
yield return rest;
}
copy.Insert(0, i);
}
}
}
我们做得怎么样？
通过了 3 项要求中的 2 项。我的目标是 100%，所以它失败了
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 失败
- 速度：快 - 勉强通过
2. 使用 WPF 拼写检查器
我知道 WPF 支持拼写检查器。此控件的诀窍在于它需要在STA 线程[^]中运行。
以下是使用 WPF 拼写检查器的示例
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Windows.Controls;
using System.Windows.Documents;
namespace FastAnagrams
{
static class Program
{
private static void Main()
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
var sh = new SpellCheckHelper();
IEnumerable<string> anagrams = null;
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Start();
sh.BeginBulkFind(Anagrams(lookupWord));
anagrams = sh.EndBulkFind();
elapsed = st.Elapsed;
st.Stop();
Console.WriteLine($"Time: {elapsed.TotalMilliseconds} ms");
Console.WriteLine($"{anagrams.Count():N0} valid anagrams\r\n");
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
}
}
public class SpellCheckHelper
{
private readonly object sync = new object();
private List<string> validWords = new List<string>();
private IEnumerable<string> words;
private bool inProgress;
private bool isComplete;
public bool IsComplete => isComplete;
public void BeginBulkFind(IEnumerable<string> words)
{
this.words = words;
validWords.Clear();
var backgroundThread
= new Thread(new ThreadStart(DoBulkCheck));
backgroundThread.SetApartmentState(ApartmentState.STA);
backgroundThread.Start();
isComplete = false;
inProgress = true;
}
public List<string> EndBulkFind()
{
lock (sync) if (!isComplete) Monitor.Wait(sync);
isComplete = false;
inProgress = false;
return validWords;
}
private void DoBulkCheck()
{
try
{
var tb = new TextBox();
tb.SpellCheck.IsEnabled = true;
foreach (var word in words)
{
int index = 0;
tb.Text = word;
var valid = true;
while ((index =
tb.GetNextSpellingErrorCharacterIndex
(index, LogicalDirection.Forward)) != -1)
if (!string.IsNullOrEmpty
(tb.Text.Substring(index,
tb.GetSpellingErrorLength(index))))
{
valid = false;
break;
}
if (valid) validWords.Add(word);
}
}
finally
{
lock (sync)
{
isComplete = true;
Monitor.PulseAll(sync);
}
}
}
}
}
我们做得怎么样？
通过了 3 项要求中的 2 项。性能至关重要，因此在 38 秒以上失败
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 通过
- 快 - 失败
3. 使用自定义拼写检查器检查有效单词
使用 WPF 拼写检查器逐个单词检查太慢了。所以让我们加载一个单词列表，然后针对我们的列表运行检查。
快速搜索找到了已编译单词列表：GitHub - 350k+ 英语单词[^]。
接下来，我们需要一种快速的方法来检查单词是否在 `List` 中。 泛型 HashSet<T> 类[^]“基于数学集合模型，并提供高性能的集合操作，类似于访问 Dictionary<TKey, TValue> 或 HashTable 集合的键”。这是修订后的版本
static class Program
{
private static void Main(string[] args)
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
var anagrams = new List<string>();
st.Start();
LoadWords("words.txt");
st.Stop();
Console.WriteLine($"Loading Time: {st.ElapsedMilliseconds} ms\r\n");
var prime = "a".Anagrams();
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
anagrams.Clear();
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Start();
var words = Anagrams(lookupWord);
foreach (var item in words)
{
if (wordList.Contains(item))
anagrams.Add(item);
}
elapsed = st.Elapsed;
st.Stop();
Console.WriteLine($"Time: {elapsed.TotalMilliseconds} ms");
Console.WriteLine($"{anagrams.Count:N0} valid anagrams out of {words.Count():N0}\r\n");
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
}
}
static HashSet<string> wordList = new HashSet<string>();
static void LoadWords(string filename)
{
string word = string.Empty;
using (StreamReader sr = File.OpenText(filename))
while ((word = sr.ReadLine()) != null)
if (word.Length > 0 && !word.Contains("'") && !word.Contains("\""))
wordList.Add(word);
}
}
我们做得怎么样？
以 2.75 毫秒的合理性能通过了 3 项要求中的 3 项
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 通过
- 速度：快 - 通过
这是一个可行的解决方案。但我们能做得更快吗？
4. 改变解决问题的方法
在前 3 次尝试中，我们生成了一个需要根据字典或单词列表进行验证的字谜列表。这需要时间来生成并验证每个单词。
一个更简单的方法是预先生成字谜集并查找每个集。这样，我们就可以节省生成和验证的时间。我们可以将字谜集存储在 泛型 Dictionary<TKey, TValue> 类[^] 中，并计算一个对字谜集中的每个字谜都通用的键。
计算通用键经历了几个迭代，获胜的解决方案基于“所有单词的字谜长度相同且包含相同的字符”。
因此，例如，“teaser”，“eaters”，“easter”，“asteer”，“aretes”，“saeter”，“seater”，“staree”，“reseat”都具有相同的键“aeerst”。
static string GetKey(string w)
{
var chars = w.ToCharArray();
Array.Sort(chars);
return new string(chars);
}
我们现在不需要生成字谜列表。将要加载的单词列表包含我们需要的所有单词。预先构建我们的字谜列表并将其存储在具有我们生成的键的 `Dictionary<TKey, TValue>` 中，意味着我们可以获取用户输入的单词，生成一个键，并在该单词有效的情况下批量获取有效的字谜列表。
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
namespace FastAnagrams
{
static class Program
{
private static void Main(string[] args)
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
IEnumerable<string> anagrams = null;
st.Start();
LoadWords("words.txt");
st.Stop();
Console.WriteLine($"Loading Time: {st.ElapsedMilliseconds} ms\r\n");
var prime = ContainsWord("a");
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Start();
var key = lookupWord.GetKey();
if (ContainsWord(key)) anagrams = GetResults(key);
elapsed = st.Elapsed;
st.Stop();
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
Console.WriteLine($"\r\nTime: {elapsed.TotalMilliseconds} ms");
Console.WriteLine($"{count:N0} anagrams for {lookupWord}");
}
}
static bool ContainsWord(string key) => LookupTable.ContainsKey(key);
static IEnumerable<string> GetResults(string key) => LookupTable[key];
static Dictionary<string, list<string>> LookupTable
= new Dictionary<string, list<string>>();
static 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];
}
wordList.Add(word);
}
}
}
}
}
}
我们做得怎么样？
在性能方面有重大改进，以 0.0148 毫秒的速度通过了 3 项要求中的 3 项
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 通过
- 速度：更快 - 通过
这是一个好得多的解决方案。但我们能做得更快吗？
5. 性能调整
现在，您可能认为我们无法进一步调整性能。但通过一点实验，这是可能的。目前，代码执行 3 个函数调用
- 生成键
- 检查键是否存在
- 返回字谜列表
通过将这 3 个函数合并为一个，我们实现了性能的又一次重大飞跃。最终版本现在是
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
namespace FastAnagrams
{
static class Program
{
private static void Main(string[] args)
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
IEnumerable<string> anagrams = null;
st.Start();
LoadWords("words.txt");
st.Stop();
Console.WriteLine($"Loading Time: {st.ElapsedMilliseconds} ms\r\n");
var prime = Find("a");
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Restart();
anagrams = Find(lookupWord);
elapsed = st.Elapsed;
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
Console.WriteLine($"\r\nTime: {elapsed.TotalMilliseconds} ms");
Console.WriteLine($"{count:N0} anagrams for {lookupWord}");
}
}
public static string GetKey(this string word)
{
var chars = word.ToCharArray();
Array.Sort(chars);
return new string(chars);
}
static IEnumerable<string> Find(string lookupWord)
{
var chars = lookupWord.ToCharArray();
Array.Sort(chars);
var key = new string(chars);
if (LookupTable.ContainsKey(key))
foreach (var item in LookupTable[key])
yield return item;
else
yield break;
}
static Dictionary<string, list<string>> LookupTable
= new Dictionary<string, list<string>>();
static 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];
}
wordList.Add(word);
}
}
}
}
}
}
我们做得怎么样？
通过了 3 项要求中的 3 项！
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 通过
- 速度：如火如荼！- 通过
我们赢了！从最初的 2.75 毫秒（已验证单词）到 0.0003 毫秒。
6. 特别提及 - SQLite
我预计 SQLite[^] 比内存查找表会慢一些。对于我的 Macbook Pro 及其 SSD（固态硬盘），结果令人惊讶 - 它们与优化后的字典方法（5.）一样快！
using System;
using System.Collections.Generic;
using System.Data.SQLite;
using System.Diagnostics;
using System.IO;
using System.Text;
namespace FastAnagrams
{
static class Program
{
private static void Main(string[] args)
{
var st = new Stopwatch();
var elapsed = default(TimeSpan);
IEnumerable<string> anagrams = null;
st.Start();
InitDB();
st.Stop();
while (true)
{
st.Reset();
Console.Write("\r\nSearch Word: ");
int count = 0;
var lookupWord = Console.ReadLine().Trim().ToLower();
if (lookupWord.Length == 0) break;
st.Restart();
anagrams = Find(lookupWord);
elapsed = st.Elapsed;
foreach (var anagram in anagrams)
Console.WriteLine($"{++count,2}: {anagram}");
Console.WriteLine($"\r\nTime: {elapsed.TotalMilliseconds} ms");
Console.WriteLine($"{count:N0} anagrams for {lookupWord}");
}
}
public static string GetKey(this string word)
{
var chars = word.ToCharArray();
Array.Sort(chars);
return new string(chars);
}
static IEnumerable<string> Find(string lookupWord)
{
var chars = lookupWord.ToCharArray();
Array.Sort(chars);
using (var cmd =
new SQLiteCommand($"SELECT word FROM {tableName} WHERE '" +
new string(chars) + "' = wordkey", dbConn))
using (SQLiteDataReader coreReader = cmd.ExecuteReader())
while (coreReader.Read())
yield return coreReader[0].ToString();
}
static SQLiteConnection dbConn;
static SQLiteTransaction dbTrans;
static string wordFile = "words.txt", dbFile = "words.db",
conn, tableName = "WordLookup",
createCmd = $"CREATE TABLE {tableName} (wordkey TEXT, word TEXT)",
insertCmd = $"INSERT INTO {tableName} (wordkey, word) values (@wordkey, @word)";
static void InitDB()
{
CheckAndOpenDb(dbFile);
CheckAndCreateTable();
}
private static void CheckAndOpenDb(string file)
{
conn = $"Data Source={file};Version=3;DateTimeKind=Utc";
if (!File.Exists(file))
{
Console.WriteLine("Creating Database...");
SQLiteConnection.CreateFile(file);
}
else
{
Console.WriteLine("Starting DB...");
}
dbConn = new SQLiteConnection(conn);
dbConn.Open();
}
private static void CheckAndCreateTable()
{
if (!TableExists(tableName))
{
Console.WriteLine("Creating Table...");
ExecuteCommand(createCmd);
LoadWords();
}
}
static void LoadWords()
{
string word, key;
Console.WriteLine("Copying Word.Txt to Table...");
BeginTrans();
using (StreamReader sr = File.OpenText(wordFile))
{
while ((word = sr.ReadLine()) != null)
{
if (word.Length > 0 &&
!word.Contains("'") &&
!word.Contains("\""))
{
key = word.GetKey();
ExecuteCommand(insertCmd,
new Dictionary<string, object>
{
{ "@wordkey", key },
{ "@word", word }
});
}
}
}
CommitTrans();
}
static bool ExecuteCommand
(string query, Dictionary<string, object> fields = null)
{
bool success = false;
using (SQLiteCommand cmd = Command(query))
{
if (fields != null && fields.Count != 0)
foreach (var key in fields.Keys)
cmd.Parameters.AddWithValue(key, fields[key]);
cmd.ExecuteNonQuery();
success = true;
}
return success;
}
static SQLiteCommand Command(string sql)
{
return new SQLiteCommand(sql, dbConn);
}
static bool TableExists(string name)
=> Command($"SELECT name FROM sqlite_master
WHERE type='table' AND name='{name}'")
.ExecuteReader()
.HasRows;
static void BeginTrans()
{
dbTrans = dbConn.BeginTransaction();
}
static void CommitTrans()
{
dbTrans.Commit();
}
}
}
我们做得怎么样？
通过了 3 项要求中的 3 项。
- 生成字谜 - 通过
- 有效（拼写检查）单词 - 通过
- 速度：如火如荼！- 通过
结果总结
Loading words...
3. Anagram using HashSet
4. Keyed Dictionary
5. Keyed Dictionary Optimised
6. SqLite Lookup
Running Tests...
Name Count Timing (ms) % Var
----------------------------------------------------------------------
1. Anagram Generator 360 3.83040 0.00000
2. Anagram WPF Spell Check 3 38,484.62290 -99.99005
3. Anagram using HashSet 9 2.75240 39.16582
4. Keyed Dictionary 9 0.01480 25,781.08108
5. Keyed Dictionary Optimised 9 0.00030 1,276,700.00000
6. SqLite Lookup 9 0.00030 1,276,700.00000
----------------------------------------------------------------------
* Timings are dependant on the config of the PC running them.
-- press any key to exit --
WPF 单词词典似乎比用于测试 3 到 6 的单词列表要小。单词“teaser”只找到 3 个字谜，测试 3 到 9 找到 9 个。SqLite 测试起初让我感到困惑，但后来经过独立检查和验证。所有测试均在 Release 模式下进行，并从命令行运行。
结语
这段旅程很有趣。从这次旅程中学到的教训是，不要在未经验证的情况下就否定可能的解决方案。考虑到我电脑的配置，我从未想过 SQLite 解决方案会如此之快。在实际场景中，结果将根据其运行的系统而有所不同。
包含可下载代码
本文包含的代码是共享的，可以单独运行，也可以作为一个测试解决方案一起运行。
为了进行最佳测试，就像本文所做的那样，请在 Release 模式下编译代码，打开命令提示符并运行。