Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > быстрый поиск

Автор: TupleCa 9.12.2006, 14:29

в файле d.dat содержится 181440 полей. (в дальнейшем надо около 1 триллиона)
вот код, как я ищу нужную строку по заданному ключу m

Код


        Properties ht = new Properties();        
        FileInputStream fin = null;
        try{
            fin=new FileInputStream("dict\\d.dat");
        }
        catch(FileNotFoundException e){
            
        }
        try{
            if(fin!=null){
                ht.load(fin);
                fin.close();
            }
        }
        catch(IOException e){
            System.out.println("Error read file");
        }
        String put=(String)ht.get(m);
        StringBuffer str=new StringBuffer(put);
        str.reverse();        
        System.out.println(str);

Время поиска : 920.880383 миллисеунд. Примерно 0.920 секунды

Это УЖАСНО долго на самом деле. нужно не более чем 0.1 секунда.

я думаю что основное время затрачивается на

Код


         ht.load(fin);

потому-что каждый раз при исполнении. это выполняется.

вопрос 1: можно ли как-то сразу при компиляции загрузить этот файд d.dat. что бы исполнении его уже не надо было загружать.
вопрос 2: какой есть более эффективный способ хранения информации, что бы затраты(по времени) на поиск нужного значения были сведены к минимуму.

Автор: shimopus 9.12.2006, 14:35

1. А зачем при компиляции? Можно при запуске сразу считывать его, но это будет неоправданно, на мой взгляд, забивать ОП. Особенно, когда там будет триллион записей. А при компиляции - это сразу же создать явно переменную, проинициализированную информацией из d.dat
2. Ну самый быстрый - это в ОП. Из других... может быть БД?

Автор: powerOn 9.12.2006, 14:37

Цитата(TupleCa @ 9.12.2006, 14:29

)

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

Используйте индексирование. При нем, сначало строится оптимизированный файл индекса. А поиск происходит только по нему (индексу).
Вот вам в помощь http://lucene.apache.org/.

Автор: TupleCa 9.12.2006, 16:33

как вот это

Код


        ht.load(fin);

выполнить сразу при объявлении ht.
d.dat 6мб, впринцыпе для меня это не критично.
зато скорость 0.360242 миллисеунд.

Автор: _Y_ 9.12.2006, 19:49

Когда-то, лет 12 назад, на первом еще VB я столкнулся с проблемой булева поиска в текстовой БД. На тот момент и память была маленькой и процессор быстро информацию не жевал. Решение было примерно такое:

Файл был единый, но грузился не целиком, а по блокам, ну, скажем по N строк.
Блок грузился и объединялся в сплошной текст с разделительными, текстовыми же, символами.
Велся поиск в этой одной огромной "строке".
Если нужное не находилось - грузился следующий блок.
Записи, естественно, лежали в файле упорядоченно и грузился не первый блок, а блок наиболее вероятно содержащий искомую информацию.
При новом поиске сначала обыскивался блок уже лежащий в памяти (все равно уж он там); это часто помогало точнее определить какой блок грузить следующим.

Звучит все это, конечно, дико, но народ приходил ко мне удивляться как быстро эта крокозябра работала.

Автор: LSD 10.12.2006, 13:20

По моему в данном случае явное непонимание, того как это все должно работать. В данном случае без индекса не обойтись, можно его делать руками, как описал _Y_. Можно использовать готовы решения типа Apache Lucene. А можно просто использовать механизм индексирования СУБД.

P.S. Прикола ради посчитай сколько это 1 триллион записей по 10 байт ;)

Автор: Tony 11.12.2006, 00:53

Бери FileChanel класс. И 4итай нужное коли4ество байт а не всю строку за раз.

ID 32(bytes) stroka(255bytes)
dfmg493t04kdhfgdfh...............Moja.stroka........
893bg8gb43t934t43...............Stoka.nomer.2....

Так вот во время 4теня ты 4итешь 32 байта если ID=запросу ID, to 4итаешь следующие 255 байт. Если не равны то пропускаеш 255 байт fileChanel.position(fileChannel.position()+255).