Лжеотождествление электровиолончели

[k0ldbl00d]

Так вот как Фокс Йовович составлял свои письма!

[mOlind]

Порадовала элегантность решения. Функциональный подход во всей красе.

[xappymah]

Огромный простор для стеганографии. Передача бинарных данных через хешкоды нагенерированных строк, например.

[janatem]

Если 31 возводить в степень n не за n умножений, а за очевидные log(n), то насколько уменьшится общее время работы?

[tagir_valeev]

Сделайте и замерьте :-) Можно ещё проще поступить — насчитать все нужные степени в таблицу, их немного. Будет ещё быстрее. А ещё вероятно стоит освоить деление в кольце вычетов. Думаю, для конкретных констант (31 и 2³²) можно получить конкретную формулу. Тогда по всем длинам пробегаться не придётся, будет ещё быстрее.

В данном случае задача одноразовая, поэтому общее время складывается из времени работы программы и времени работы программиста.

[hellman]

Думаю, для конкретных констант (31 и 2^32) можно получить конкретную формулу

Просто нужно умножать на обратный к 31 элемент (3186588639).

[tagir_valeev]

Ага, только учесть, что в Java int знаковый. Чуть раньше до того же дошёл :-)

[tagir_valeev]

Собственно, идея с дискретным делением оказалась не такая сложная. Умножению на 31 для чисел int обратной операцией будет умножение на -1108378657 (удивительно, правда?). Можно переписать программу так:

import java.nio.charset.Charset;
import java.nio.file.*;
import java.util.*;
import java.util.stream.*;

public class PhraseHashCode3 {
    public static void main(String[] args) throws Exception {
        int target = Integer.MIN_VALUE;
        String[] preps = { "в", "и", "с", "по", "на", "под", "над", "от", "из",
                "через", "перед", "за", "до", "о", "не", "или", "у", "про", "для" };
        List<String> infixes = Stream.concat(Stream.of(" "), Arrays.stream(preps).map(p -> ' '+p+' '))
                .collect(Collectors.toList());
        List<String> words = Files.readAllLines(Paths.get("litf-win.txt"), Charset.forName("cp1251")).stream()
                .map(s -> s.substring(0, s.indexOf(' ')))
                .filter(s -> s.length() > 2)
                .collect(Collectors.toList());
        Map<Integer, List<String>> hashPrefix = words.stream()
                .map(s -> Character.toTitleCase(s.charAt(0)) + s.substring(1))
                .collect(Collectors.groupingBy(String::hashCode));
        words.stream()
                .flatMap(s -> infixes.stream().map((String infix) -> infix+s))
                .flatMap(s -> hashPrefix.getOrDefault(
                            IntStream.range(0, s.length()).reduce(target - s.hashCode(), (a, i) -> a*-1108378657), 
                            Collections.emptyList()).stream().map(prefix -> prefix+s))
                .sorted().forEach(System.out::println);
    }
}

Результат такой же, зато и короче, и быстрее (у меня раза в 4-5 прирост скорости).

[DreamWalker]

Надо будет на досуге подобную штуку для .NET сделать. Но только там алгоритм сложнее: хэши считаются отдельно по чётным и нечётным символам + есть XOR. На коленке сходу удалось подобрать лишь два примера:

"утопист забутка".GetHashCode() == "бодунья носки".GetHashCode() == 0

[DreamWalker]

Прошу прощения, это для нуля. Вот int.MinValue:

"вручить подкрякивать".GetHashCode() == int.MinValue

[turbo_exe]

пост превосходства программистов над php девелоперами, клепающими формочки.
_{*написано php девелопером}