Comments 11
Так вот как Фокс Йовович составлял свои письма!
+13
Порадовала элегантность решения. Функциональный подход во всей красе.
+2
Огромный простор для стеганографии. Передача бинарных данных через хешкоды нагенерированных строк, например.
+3
Если 31 возводить в степень n не за n умножений, а за очевидные log(n), то насколько уменьшится общее время работы?
0
Сделайте и замерьте :-) Можно ещё проще поступить — насчитать все нужные степени в таблицу, их немного. Будет ещё быстрее. А ещё вероятно стоит освоить деление в кольце вычетов. Думаю, для конкретных констант (31 и 232) можно получить конкретную формулу. Тогда по всем длинам пробегаться не придётся, будет ещё быстрее.
В данном случае задача одноразовая, поэтому общее время складывается из времени работы программы и времени работы программиста.
В данном случае задача одноразовая, поэтому общее время складывается из времени работы программы и времени работы программиста.
+2
Собственно, идея с дискретным делением оказалась не такая сложная. Умножению на 31 для чисел int обратной операцией будет умножение на -1108378657 (удивительно, правда?). Можно переписать программу так:
Результат такой же, зато и короче, и быстрее (у меня раза в 4-5 прирост скорости).
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 прирост скорости).
+2
Надо будет на досуге подобную штуку для .NET сделать. Но только там алгоритм сложнее: хэши считаются отдельно по чётным и нечётным символам + есть XOR. На коленке сходу удалось подобрать лишь два примера:
"утопист забутка".GetHashCode() == "бодунья носки".GetHashCode() == 0
+1
пост превосходства программистов над php девелоперами, клепающими формочки.
*написано php девелопером
*написано php девелопером
-6
Sign up to leave a comment.
Лжеотождествление электровиолончели