Можно ли ещё оптимизировать текстовое задание??

Question

[artshelom]

Можно ли ещё увеличить скорость выполнения этого кода?

Задача:
Японцы бесконечно влюблены в технику, которая их окружает. Они внимательно следят за всеми техническими новинками и стараются пользоваться самыми современными и «умными» из них. У Дена и Сергея есть гениальный план: они хотят создать текстовый редактор, который покорит японцев. Важнейшей уберинтеллектуальной функцией редактора должна стать функция автодополнения. Если пользователь набрал несколько первых букв слова, редактор должен предложить ему самые правдоподобные окончания.
Ден и Сергей уже собрали огромное количество японских текстов. Для каждого слова японского языка они посчитали число раз, которое оно встречается в текстах. Если пользователь уже ввел несколько букв, то редактор должен показать не более десяти самых часто употребляемых слов, начинающихся со введенных пользователем букв, отсортированных по убыванию частоты упоминания.
Помогите Сергею с Деном перевернуть рынок текстовых редакторов.
Исходные данные
В первой строке находится единственное число N (1 ≤ N ≤ 105) — количество слов в найденных текстах. Каждая из следующих N строк содержит слово wi (непустая последовательность строчных латинских букв длиной не более 15) и целое число ni (1 ≤ ni ≤ 106) — число раз, которое встречается это слово в текстах. Слово и число разделены единственным пробелом. Ни одно слово не повторяется более одного раза. В (N + 2)-й строке находится число M (1 ≤ M ≤ 15000). В следующих M строках содержатся слова ui (непустая последовательность строчных латинских букв длиной не более 15) — начала слов, введенных пользователем.

Можно ли ещё оптимизировать данный код:

private List<StringIntObj> sort(List<StringIntObj> list){//StringIntObj- это объект который содержит слово и мощность этого слова
        List<StringIntObj> sortList = new ArrayList<>(10);
        if (list==null||list.size()==0)
            return null;
        StringIntObj bottom = list.get(0);
        for (int i=0;i<list.size();i++){
            if (sortList.size()<10){
                sortList.add(list.get(i));
                if (bottom.compareTo(list.get(i))>0)
                    bottom = list.get(i);//Находит минимум из 1 десяти!
            }else{
                if (bottom.compareTo(list.get(i))<0)
                    continue;
                Collections.sort(sortList);
                if (sortList.get(9).compareTo(list.get(i))>0)
                    sortList.set(9, list.get(i));
                for (int a=0;a<sortList.size()-1;a++){
                    if (sortList.get(a).compareTo(list.get(i))>0&&sortList.get(a+1).compareTo(list.get(i))<0){
                        sortList.set(a, list.get(i));
                        bottom=sortList.get(0);
                        break;
                    }
                }
            }
        }
        return sortList;
    }


    private String parsText(String word){//Ищет подходящие слова, если их не находит возвращает пустой массив.
        List<StringIntObj> list = sort(tree.search(word));
//        List<StringIntObj> list = (tree.search(word));
        //Если использовать в сортировки TreeSet то время увеличиться до 25 секунд. Так что нужно дальше думать!
        StringBuffer buffer = new StringBuffer();
        if (list == null||list.size()==0)
            return null;
        Collections.sort(list);
        for (int i = 0;i<10&&i<list.size();i++){
            buffer.append(list.get(i).get()).append(" ");
        }
        return String.valueOf(buffer);
    }

Answer 1

[longclaps]

Джавист из меня никакой, решил попрактиковаться.
Вот тебе java-реализация на HashMap, переписанная с питонной:

import java.io.*;
import java.util.*;

class CountedWord {
    int c;
    String w;

    public CountedWord(String s) {
        String[] l = s.split(" ", 2);
        this.c = Integer.parseInt(l[1]);
        this.w = l[0];
    }
}

public class Main {
    public static int TEN = 10;

    public static void main(String[] args) throws Exception {
        long start = System.nanoTime();
        HashMap<String, CountedWord[]> prefixMap = new HashMap<>();
        BufferedReader data = new BufferedReader(new FileReader("test.in"), 0x10000);
        for (int i = Integer.parseInt(data.readLine()); i > 0; i--) {
            CountedWord cw = new CountedWord(data.readLine());
            String prefix = cw.w;
            for (int le = prefix.length() - 1; le >= 0; le--) {
                CountedWord[] buf = prefixMap.get(prefix);
                if (buf == null) {
                    buf = new CountedWord[TEN];
                    buf[0] = cw;
                    prefixMap.put(prefix, buf);
                } else { // это даже не сортировка вставкой, а просто вставка
                    int j = TEN - 1;
                    if (buf[j] != null && cw.c <= buf[j].c)
                        break; // уже на этом префиксе cw.c оказался меньше всех
                    while (buf[--j] == null) ;
                    j++;
                    while (j-- > 0 && buf[j].c < cw.c) buf[j + 1] = buf[j];
                    buf[j + 1] = cw;
                }
                prefix = prefix.substring(0, le);
            }
        }

        for (int i = Integer.parseInt(data.readLine()); i > 0; i--) {
            String prefix = data.readLine();
            System.out.println(String.format("     ~ %s", prefix));
            CountedWord[] buf = prefixMap.get(prefix);
            if (buf == null) continue;
            for (int j = 0; j < TEN; j++) {
                CountedWord cw = buf[j];
                if (cw == null) break;
                System.out.println(String.format("%6d %s", cw.c, cw.w));
            }
        }
        System.out.println(String.format(
                "\nit takes %.3f sec", 1e-9 * (System.nanoTime() - start)));
    }
}

Comments

[artshelom]

Классное решение. Если вы не против, я выложу около своего решения ваше с ссылкой на ваш этот акк??

[longclaps]

artshelom: Делай что хочешь.