Самый быстрый способ найти самую длинную строку из набора, содержащегося во входной строке - PullRequest
Новая
       17

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

0 голосов
/ 07 марта 2019

У меня есть очень большой List<MyClass> (приблизительно 600.000 записей +), в котором мне нужно извлечь запись, где MyClass.Property1 - точное совпадение или ближайшая к моей входной строке. Однако, даже если это кажется, это не проблема нечеткого сопоставления строк, поэтому я не могу использовать расстояние Левенштейна. Чтобы немного прояснить ситуацию, приведу пример.

Предположим, что мой набор данных содержит следующее (только список MyClass.Property1): 

242
2421    
2422    
24220   
24221   
24222   
24223   
24224

Теперь то, что я ожидаю, если я имею на входе 2422, я ожидаю, что третья запись будет дана на выходе. Если я попадаю на вход 24210, я ожидаю на выходе вторую запись, которая является самой длинной строкой, содержащейся в моем выводе. Чтобы ускорить процесс, когда я заполняю List<MyClass>, я сохранил в Dictionary<int,int> индекс, при котором изменяется первое число в строке (например, с 19999 до 20000), чтобы я мог уменьшить размер набора данных i. собираюсь искать совпадение. Что мне интересно: какой самый быстрый способ достичь моей цели?

Единственное, о чем я могу думать, это что-то вроде этого:

Так как я уверен, что List<MyClass> упорядочен по MyClass.Property1, как в примере, и предположим, что я извлек List<MyClass> с именем SubSet на основе словаря, который я упомянул ранее, я бы сделал 

MyClass result = null;
foreach(MyCLass m in SubSet)
{
    if (input.Contains(m.Property1))
    {
       // if the 2 strings are equal i've found the exact match
       if(input == m.Property1)
         return m.Property1;
       else
         result = m;            
    }
    else
       return result;
}

Самая очевидная проблема, которую я вижу здесь, заключается в том, что если желаемый результат находится в конце SubSet, мне нужно перебрать тысячи записей. Можете ли вы придумать какой-нибудь лучший способ достичь своей цели или способ улучшить мой текущий код?

1 Ответ

0 голосов
/ 07 марта 2019

Может быть, вы можете использовать метод Linq в рекурсивной функции, такой как 

public string test(string input)
{
    string result = Subset.FirstOrDefault(a => a == input);
    if (result == null)
        return test(input.Substring(0, input.Length - 2));
    else
        return result;
}
...