Алгоритм поиска в несортированном списке слов - C#
Формулировка задачи:
Имеется неотсортированный список слов, порядка миллиона. Какой лучше использовать алгоритм чтобы найти, допустим, слово "Мир"? Есть ограниченкие - выдать результат не более 10 сек
Решение задачи: «Алгоритм поиска в несортированном списке слов»
textual
Листинг программы
using System.Linq;
using System;
using System.Collections;
using System.Collections.Generic;
namespace ConsoleApplication1
{
public class HTable
{
object[] values;
public int Count = 0;
public HTable(int n)
{
values = new object[n];
}
/// <summary>
/// Возвращает хеш-код по переданному в него элементу
/// </summary>
/// <param name="val">Хешируемый элемент</param>
/// <param name="collision">Если true, то разрешает коллизии, если False, то ищет пустую ячейку для элемента</param>
/// <returns></returns>
private int GetHash(object val, bool collision)
{
if (Count == values.Length)
return -1;
int x = val.ToString().Aggregate(0, (acc, i) => acc + i) % values.Length; //берем сумму кодов каждого символа в строке и делим на размерность массива
if (!collision)
{
while (values[x] != null) //пока не наткнемся на пустую ячейку, увеличиваем счетчик на 1
{
if (val.ToString() == values[x].ToString()) //если наткнулись на точно такой же элемент, то возвращаем -1, дабы избавиться от одинаковых элементов в таблице
return -1;
x = x + 1 >= values.Length ? 0 : x + 1; //если x + 1 больше размера таблицы, то присваиваем ему 0, иначе x + 1
}
return x;
}
else
{
int count = 0;
while (true)
{
if (count >= Count) //если перебор произвелся больше раз, чем имеется элементов, значит элемент отсутствует
return -1;
if (values[x] == null) //если ячейка пуста, то увеличиваем x на 1 по тому же принципу
x = x + 1 >= values.Length ? 0 : x + 1;
else
if (values[x].ToString() == val.ToString()) //иначе, если элемент соответствует искомому, то возвращаем его
return x;
else
x = x + 1 >= values.Length ? 0 : x + 1; //иначе снова увеличиваем x
}
}
}
public bool Add(object val)
{
int index = GetHash(val, false);
if (index != -1)
{
values[index] = val;
Count++;
}
return index != -1;
}
public void Delete(object val)
{
int index = GetHash(val, true);
if (index != -1)
values[index] = null;
}
public bool Find(object finding, out object result)
{
result = null;
int index = GetHash(finding, true);
if (index != -1)
{
result = values[index];
}
return index != -1;
}
}
class Program
{
static void Main()
{
HTable h = new HTable(1000000);
string obj;
char choose;
while (true)
{
Console.Clear();
Console.WriteLine("1.Добавить\n2.Удалить\n3.Поиск\n4.Выход");
choose = Console.ReadKey().KeyChar;
Console.Clear();
switch (choose)
{
case '1':
Console.Write("*Добавление*\nВведите значение->");
obj = Console.ReadLine();
if (obj == "")
break;
Console.WriteLine("Обеъкт {0}", h.Add(obj) ? "добавлен" : "не добавлен");
Console.ReadLine();
break;
case '2':
Console.Write("*Удаление*\nВведите значение->");
h.Delete(Console.ReadLine());
break;
case '3':
Console.Write("*Поиск*\nВведите значение->");
obj = Console.ReadLine();
object result;
Console.Write(h.Find(obj, out result) ? result.ToString() + " присутствует" : "Отсутствует");
Console.ReadLine();
break;
case '4':
return;
}
}
}
}
}