Поиск нескольких HashMaps в то же время

Question

tldr: Как я могу искать запись в нескольких (только для чтения) Java HashMaps в одно и то же время?

---

Длинная версия:

У меня есть несколько словарей различных размеров, хранящихся в HashMap< String, String >. Когда они будут прочитаны, они никогда не будут изменены (строго для чтения). Я хочу проверить, был ли в каком словаре сохранена запись с моим ключом.

Мой код был изначально искал ключ, как это:

public DictionaryEntry getEntry(String key) { 
    for (int i = 0; i < _numDictionaries; i++) { 
     HashMap<String, String> map = getDictionary(i); 
     if (map.containsKey(key)) 
      return new DictionaryEntry(map.get(key), i); 
    } 
    return null; 
} 

Тогда это стало немного сложнее: моя строка поиска может содержать опечатки, или был вариант хранимой записи. Например, если сохраненный ключ был «бананом», возможно, я бы поискал «баннану» или «банан», но все равно хотел бы, чтобы запись для «банана» вернулась. Использование Левенштейна-Distance, я теперь перебрать все словари и каждую запись в них:

public DictionaryEntry getEntry(String key) { 
    for (int i = 0; i < _numDictionaries; i++) { 
     HashMap<String, String> map = getDictionary(i); 
     for (Map.Entry entry : map.entrySet) { 
      // Calculate Levenshtein distance, store closest match etc. 
     } 
    } 
    // return closest match or null. 
}  

До сих пор все работает как надо, и я получаю запись я хочу. К сожалению, мне приходится искать около 7000 строк, в пяти словарях различного размера (~ 30 - 70 тыс. Записей), и это занимает некоторое время. Из моего результата обработки у меня сильное впечатление, что мой поиск доминирует в общей среде исполнения.

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

Вопрос просто: как это сделать? Я никогда раньше не использовал многопоточность. В моем поиске появился Concurrent HashMaps (но, на мой взгляд, мне это не нужно) и Runnable-class, где мне пришлось бы поместить мою обработку в метод run(). Я думаю, что я мог бы переписать мой текущий класс, чтобы он поместился в Runnable, но мне было интересно, может быть, есть более простой способ сделать это (или как я могу это сделать просто с Runnable, сейчас мое ограниченное понимание думает, что мне нужно реструктурировать много).

---

С меня попросили поделиться Левенштейна-Logic: Это на самом деле ничего особенного, но здесь вы идете:

private int _maxLSDistance = 10; 
public Map.Entry getClosestMatch(String key) { 
    Map.Entry _closestMatch = null; 
    int lsDist; 

    if (key == null) { 
     return null; 
    } 

    for (Map.Entry entry : _dictionary.entrySet()) { 
     // Perfect match 
     if (entry.getKey().equals(key)) { 
      return entry; 
     } 
     // Similar match 
     else { 
      int dist = StringUtils.getLevenshteinDistance((String) entry.getKey(), key); 

      // If "dist" is smaller than threshold and smaller than distance of already stored entry 
      if (dist < _maxLSDistance) { 
       if (_closestMatch == null || dist < _lsDistance) { 
        _closestMatch = entry; 
        _lsDistance = dist; 
       } 
      } 
     } 
    } 
    return _closestMatch 
} 

Answer 1

Для того, чтобы использовать многопоточность в вашем случае, может быть что-то вроде :

Класс «монитор», который в основном сохраняет результаты и координирует потоки;

public class Results { 

    private int nrOfDictionaries = 4; // 

    private ArrayList<String> results = new ArrayList<String>(); 

    public void prepare() { 
     nrOfDictionaries = 4; 
     results = new ArrayList<String>(); 
    } 

    public synchronized void oneDictionaryFinished() { 
     nrOfDictionaries--; 
     System.out.println("one dictionary finished"); 
     notifyAll(); 
    } 

    public synchronized boolean isReady() throws InterruptedException { 

     while (nrOfDictionaries != 0) { 
      wait(); 
     } 

     return true; 
    } 

    public synchronized void addResult(String result) { 
     results.add(result); 
    } 

    public ArrayList<String> getAllResults() { 
     return results; 
    } 
} 

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

public class ThreadDictionarySearch extends Thread { 

    // the actual dictionary 
    private String dictionary; 
    private Results results; 

    public ThreadDictionarySearch(Results results, String dictionary) { 
     this.dictionary = dictionary; 
     this.results = results; 
    } 

    @Override 
    public void run() { 

     for (int i = 0; i < 4; i++) { 
      // search dictionary; 
      results.addResult("result of " + dictionary); 
      System.out.println("adding result from " + dictionary); 
     } 

     results.oneDictionaryFinished(); 
    } 

} 

И основной метод для демонстрации:

public static void main(String[] args) throws Exception { 

    Results results = new Results(); 

    ThreadDictionarySearch threadA = new ThreadDictionarySearch(results, "dictionary A"); 
    ThreadDictionarySearch threadB = new ThreadDictionarySearch(results, "dictionary B"); 
    ThreadDictionarySearch threadC = new ThreadDictionarySearch(results, "dictionary C"); 
    ThreadDictionarySearch threadD = new ThreadDictionarySearch(results, "dictionary D"); 

    threadA.start(); 
    threadB.start(); 
    threadC.start(); 
    threadD.start(); 

    if (results.isReady()) 
    // it stays here until all dictionaries are searched 
    // because in "Results" it's told to wait() while not finished; 

for (String string : results.getAllResults()) { 
     System.out.println("RESULT: " + string); 
    } 

Answer 2

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

public DictionaryEntry getEntry(String key) { 
    for (int i = 0; i < _numDictionaries; i++) { 
    HashMap<String, String> map = getDictionary(i); 

    map.entrySet().parallelStream().foreach((entry) -> 
            { 
             // Calculate Levenshtein distance, store closest match etc. 
            } 
    ); 
    } 
    // return closest match or null. 
} 

Если вы используете java 8, конечно. Вы также можете обернуть внешний цикл в IntStream. Также вы можете напрямую использовать Stream.reduce, чтобы получить запись с наименьшим расстоянием.

Answer 3

Может попробовать пулы потоков:

ExecutorService es = Executors.newFixedThreadPool(_numDictionaries); 
for (int i = 0; i < _numDictionaries; i++) { 
    //prepare a Runnable implementation that contains a logic of your search 
    es.submit(prepared_runnable); 
} 

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

Answer 4

У меня есть свои сильные сомнения в том, что HashMaps - подходящее решение здесь, особенно если вы хотите иметь некоторые пушистые слова и слова остановки. Вы должны использовать правильные полнотекстовые поисковые решения, такие как ElaticSearch или Apache Solr или, по крайней мере, доступный движок вроде Apache Lucene.

Это означает, что вы можете использовать версию бедного человека: создайте массив ваших карт и SortedMap, выполните итерацию по массиву, возьмите ключи текущего HashMap и сохраните их в SortedMap с индексом их HashMap , Чтобы получить ключ, вы сначала выполните поиск в SortedMap для указанного ключа, получите соответствующий HashMap из массива, используя позицию индекса, и найдите ключ только в одном HashMap. Должна быть достаточно быстрой, без необходимости нескольких потоков, чтобы прорываться через HashMaps. Однако вы можете сделать код ниже в runnable, и вы можете иметь несколько поисков параллельно.

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.SortedMap; 
import java.util.TreeMap; 

public class Search { 

    public static void main(String[] arg) { 

     if (arg.length == 0) { 
      System.out.println("Must give a search word!"); 
      System.exit(1); 
     } 

     String searchString = arg[0].toLowerCase(); 

     /* 
     * Populating our HashMaps. 
     */ 
     HashMap<String, String> english = new HashMap<String, String>(); 
     english.put("banana", "fruit"); 
     english.put("tomato", "vegetable"); 

     HashMap<String, String> german = new HashMap<String, String>(); 
     german.put("Banane", "Frucht"); 
     german.put("Tomate", "Gemüse"); 

     /* 
     * Now we create our ArrayList of HashMaps for fast retrieval 
     */ 

     List<HashMap<String, String>> maps = new ArrayList<HashMap<String, String>>(); 
     maps.add(english); 
     maps.add(german); 


     /* 
     * This is our index 
     */ 
     SortedMap<String, Integer> index = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER); 


     /* 
     * Populating the index: 
     */ 
     for (int i = 0; i < maps.size(); i++) { 
      // We iterate through or HashMaps... 
      HashMap<String, String> currentMap = maps.get(i); 

      for (String key : currentMap.keySet()) { 
       /* ...and populate our index with lowercase versions of the keys, 
       * referencing the array from which the key originates. 
       */ 
       index.put(key.toLowerCase(), i); 
      } 

     } 


     // In case our index contains our search string... 
     if (index.containsKey(searchString)) { 

      /* 
      * ... we find out in which map of the ones stored in maps 
      * the word in the index originated from. 
      */ 
      Integer mapIndex = index.get(searchString); 

      /* 
      * Next, we look up said map. 
      */ 
      HashMap<String, String> origin = maps.get(mapIndex); 

      /* 
      * Last, we retrieve the value from the origin map 
      */ 

      String result = origin.get(searchString); 

      /* 
      * The above steps can be shortened to 
      * String result = maps.get(index.get(searchString).intValue()).get(searchString); 
      */ 

      System.out.println(result); 
     } else { 
      System.out.println("\"" + searchString + "\" is not in the index!"); 
     } 
    } 

} 

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

С помощью этого решения вы в основном используете скорость запуска для скорости запроса.

Answer 5

Хорошо !! ..

Поскольку ваша забота, чтобы получить быстрый ответ.

Я предлагаю вам разделить работу между потоками.

Позволяет вам иметь 5 словарей. Может содержать три словаря для одной нити, а остальные два позаботятся другой нитью. И тогда ведьма, когда нить найдет совпадение, остановит или прекратит другую нить.

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

И может быть вам нужно немного больше изменений в коде, чтобы получить близкое соответствие:

for (Map.Entry entry : _dictionary.entrySet()) { 

вы используете EntrySet Но вы не используете значения в любом случае это, кажется, получает набор входа немного дороже. И я хотел бы предложить вам просто использовать keySet, так как вы не очень заинтересованы в values в этой карте

for (Map.Entry entry : _dictionary.keySet()) { 

Для получения более подробной информации о Proformance карты Пожалуйста, прочитайте эту ссылку Map performances

итерацию над В коллекции-ссылках LinkedHashMap требуется время, пропорциональное размеру карты, независимо от ее емкости. Итерация над HashMap, вероятно, будет более дорогой, требуя времени, пропорционального ее пропускной способности.