Java: получить случайную строку из большого файла

Question

Я видел , как получить случайную строку из текстового файла , но указанный там метод (принятый ответ) работает ужасно медленно.Он работает очень медленно в моем текстовом файле объемом 598 КБ, и все еще медленно в моей версии этого текстового файла, который имеет только одну из каждых 20 строк, по 20 КБ.Я никогда не пройду через раздел «а» (это список слов).

Исходный файл содержит 64141 строк;укороченный имеет 2138 строк.Для генерации этих файлов я взял список слов Linux Mint 11 /usr/share/dict/american-english и использовал grep, чтобы удалить что-либо с заглавными буквами или апострофом (grep -v [[:upper:]] | grep -v \').

Я использую код

String result = null;
final Random rand = new Random();
int n = 0;
for (final Scanner sc = new Scanner(wordList); sc.hasNext();) {
    n++;
    if (rand.nextInt(n) == 0) {
    final String line = sc.nextLine();
        boolean isOK = true;
        for (final char c : line.toCharArray()) {
            if (!(constraints.isAllowed(c))) {
                isOK = false;
                break;
            }
        }
        if (isOK) {
            result = line;
        }
        System.out.println(result);
    }
}
return result;

, который немного адаптирован из Ответ Итая .

Объект constraints является KeyboardConstraints, который в основном имеет один метод isAllowed(char):

public boolean isAllowed(final char key) {
    if (allAllowed) {
        return true;
    } else {
        return allowedKeys.contains(key);
    }
}

, где allowedKeys и allAllowed предоставляются в конструкторе.Используемая здесь переменная constraints имеет "aeouhtns".toCharArray() в качестве allowedKeys с выключенным allAllowed.

По сути, я хочу, чтобы метод выбрал случайное слово , которое удовлетворяет ограничениям. (например, для этих ограничений будет работать «outvote», но не «работник», потому что «w» отсутствует в "aeouhtns".toCharArray()).

Как я могу это сделать?

Answer 1

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

n++;
if (rand.nextInt(n) == 0) {
    final String line = sc.nextLine();

На это (как в исходном ответе ):

n++;
final String line = sc.nextLine();
if (rand.nextInt(n) == 0) {

Вы также должны проверить ограничения перед рисованием случайного числа.Если строка не соответствует ограничениям, ее следует игнорировать, примерно так:

n++;

String line;
do {
    if (!sc.hasNext()) { return result; }
    line = sc.nextLine();
} while (!meetsConstraints(line));

if (rand.nextInt(n) == 0) {
    result = line; 
}

Answer 2

Я бы прочитал во всех строках, сохранил бы их где-нибудь, а затем выбрал бы случайную строку из этого. Это занимает тривиальное время, потому что один файл размером менее 1 МБ в наши дни является тривиальным размером.

public class Main {
    public static void main(String... args) throws IOException {
        long start = System.nanoTime();
        RandomDict dict = RandomDict.load("/usr/share/dict/american-english");
        final int count = 1000000;
        for (int i = 0; i < count; i++)
            dict.nextWord();
        long time = System.nanoTime() - start;
        System.out.printf("Took %.3f seconds to load and find %,d random words.", time / 1e9, count);
    }
}

class RandomDict {
    public static final String[] NO_STRINGS = {};
    final Random random = new Random();
    final String[] words;

    public RandomDict(String[] words) {
        this.words = words;
    }

    public static RandomDict load(String filename) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader(filename));
        Set<String> words = new LinkedHashSet<String>();
        try {
            for (String line; (line = br.readLine()) != null; ) {
                if (line.indexOf('\'') >= 0) continue;
                words.add(line.toLowerCase());
            }
        } finally {
            br.close();
        }
        return new RandomDict(words.toArray(NO_STRINGS));
    }

    public String nextWord() {
        return words[random.nextInt(words.length)];
    }
}

печать

Took 0.091 seconds to load and find 1,000,000 random words.