Как правильно реализовать Runnable для поиска элемента в Hashtable?

Таким образом, «гребень» ArrayList содержит строки одинаковой длины и вариации некоторых символов. В худшем случае этот список может содержать около 100 000 слов. Функция checkWord (String str) принимает одно слово в качестве параметра и проверяет, присутствует ли это слово в словаре Hashtable (который содержит еще 90 000 слов, текстовый файл был прочитан в эту хэш-таблицу). Таким образом, в основном код должен проверить, какой из слов из списка «гребенка» присутствует в словаре «HashTable». В худшем случае этот поиск занимает до 5 минут. Я хочу реализовать Runnable и распараллелить его, но не знаю, как это сделать.Как правильно реализовать Runnable для поиска элемента в Hashtable?

Например: список расчесок содержит различные орфографические ошибки CURMUDGEON и самого правильного слова. Этот список содержит 98415 из них. CURMUEGEON CURMUEGEOH CURMUEGEOJ CURMUEGEKN и т. Д. Поэтому, проверяя, присутствует ли каждое из этих слов в хэш-таблице, требуется 200 секунд. Я хочу, чтобы сбить этот раз

class key implements Runnable{ 
    public static ArrayList<String> comb; 
    public static Hashtable<String,String> dictionary; 
    public static void main(String[] args) throws IOException{ 
     key obj = new key(); 
     Thread thread1 = new Thread(obj); 
     thread1.start(); 
    } 
    public static Boolean checkWord(String str){ 
       String toCheck = str.toLowerCase(); 
       if(dictionary.contains(toCheck)){ 
        return true; 
       } 
       else 
       return false; 
     } 
     public void run(){ 
      for(String x:comb) 
       if (checkWord(x)) 
        filtered.add(x); 

     }

источник

2017-02-16 daipayan

При поиске 100 000 слов в HashMap должно быть порядка секунд, если это возможно. Нет смысла делать это многопоточным. Вы уверены, что «словарь» - действительно структура данных на основе хэш-таблицы? Пожалуйста, предоставьте [mcve]. –

@JonSkeet Спасибо, я отредактировал и обновил свой вопрос. – daipayan

Хмм ... 1) Почему это «Карта», а не «Набор»? Каковы значения «Карты»? 2) Параллелизация происходит за счет сложности. Если значения неактуальны, у нас есть лучшие алгоритмы для [set intersection] (http://stackoverflow.com/questions/4642172/computing-set-intersection-in-linear-time). – dhke

HashTable - это унаследованный класс API JDK1.0 с очень надежными гарантиями параллелизма. В particular,

В отличие от новых коллекционных реализаций, Hashtable синхронизирован.

Это означает, что для каждой операции на Hashtable необходимо получить блокировку монитора, которая является убийцей производительности для повторных поисков. Вероятно, лучше всего следовать рекомендациям, приведенным в javadocs JDK:

Если потоковая реализация не нужна, рекомендуется вместо Hashtable использовать HashMap. Если требуется потокобезопасная высококонкурентная реализация, тогда вместо Hashtable рекомендуется использовать ConcurrentHashMap.

источник

2017-02-16 18:51:19 dhke

Чтобы сделать это эффективно, вам необходимо иметь несколько Runnables, которые тестирования различных диапазонов списка гребенки независимо, как

public class MySearcher implements Runnable { 
    ArrayList list; 
    int startIdx, endIdx; 
    public MySearcher(list, startIdx, endIdx) { 
    // copy into object fields 
    } 
    public void run() { 
    // test all values in the list between startIdx and endIdx 
    // put results into a data structure. Create a method to get/return that data structure 
    } 
}

Затем вы можете использовать ExecutorService для всех ваши Runnables (для использования см. javadoc: http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ExecutorService.html)

источник

2017-02-16 16:50:57 ControlAltDel

Как правильно реализовать Runnable для поиска элемента в Hashtable?

ответ

Смежные вопросы