Typed Lambda Calculus in Java
Aug. 4th, 2017 01:25 am
public interface Typed {
interface Fun<A, B> {
B $(A a);
}
interface Pair<A, B, C> extends Fun<Fun<A, Fun<B, C>>, C> {
static <A, B, C> Pair<A, B, C> $(final A a, final B b) {
return p -> p.$(a).$(b);
}
static <A, B> A first(final Pair<A, B, A> p) {
return p.$(a -> b -> a);
}
static <A, B> B second(final Pair<A, B, B> p) {
return p.$(a -> b -> b);
}
}
( Read more... )
Expr<Integer> expr = fun("a", (Expr<Integer> a) ->
fun("b", (Expr<Integer> b) -> plus(a, b))
.$(1)).$(2);
// (a -> (b -> a + b) 1) 2 = 3
static void main(final String[] args) {
System.out.println(showEval(expr)
.$(s -> e -> s + " = " + e));
}
}
Untyped Lambda Calculus in Java
Jul. 30th, 2017 03:54 pm
import java.util.Objects;
public interface Untyped {
interface Lambda {
Lambda $(Lambda f);
( Read more... )
Lambda I = x -> x;
Lambda K = x -> y -> x;
Lambda S = x -> y -> z -> x.$(z).$(y.$(z));
Lambda pair = p -> a -> b -> p.$(a).$(b);
Lambda first = p -> p.$(a -> b -> a);
Lambda second = p -> p.$(a -> b -> b);
static void main(String[] args) {
print(S.$(K).$(K).$("x").equals(I.$("x")));
pair.$("x").$("y").$(first).$(print);
second.$("x").$("y").$(print);
$("x").$("y").$(first).$(print);
$("x").$("y").$(K.$(print));
}
}
JavaCartesianDualism
Nov. 9th, 2016 11:57 pmpublic class JavaCartesianDualism { // Morphism proposition is exponent interface Arrow<A, B extends A> { } // Sum proposition is dependent product interface Sum<S, A extends S, B extends S> { } // Presumably, exponent proposition is some arrow // and product proposition is some sum? interface Prod<A, B> extends Prod1<A, B>, Prod2<A, B> { } interface Prod1<A, B> { A _1(Prod<A, B> p); } interface Prod2<A, B> { B _2(Prod<A, B> p); } interface _Prod1<A, B> extends Arrow<Prod1<A, B>, Prod<A, B>> { } interface _Prod2<A, B> extends Arrow<Prod2<A, B>, Prod<A, B>> { } interface _Prod<A, B, T extends Prod<A, B>> extends Arrow<Prod<A, B>, T> { } interface Exp<A, B> { A eval(B b); } interface Curry<C, A, B> extends Exp<C, Prod<A, B>> { Exp<C, B> curry(A a); } interface _Curry<A, B, C> extends Arrow<Exp<C, Prod<A, B>>, Curry<C, A, B>> { } }
JVM escape analysis
Oct. 26th, 2016 12:19 amПродолжаю развенчивание мифов о "медленной джаве" :) Как показывает опыт, в настоящее время практически никто из широкой публики в своих рассуждениях не учитывает влияние и возможности оптимизации которая в JVM существует уже достаточно давно - а именно escape analysis. И данный факт весьма печален :(
( Например ... )
( Например ... )
Picture for strings
Oct. 22nd, 2016 03:19 amsearch size = 2097151 data size = 10 arrayBinary : 264 .. 924 arrayLinear : 152 .. 183 hashSet : 61 .. 95 treeSet : 266 .. 314 listBinary : 278 .. 369 data size = 20 arrayBinary : 294 .. 404 arrayLinear : 297 .. 399 hashSet : 59 .. 114 treeSet : 297 .. 739 listBinary : 319 .. 346 data size = 30 arrayBinary : 342 .. 410 arrayLinear : 340 .. 438 hashSet : 48 .. 70 treeSet : 341 .. 580 listBinary : 373 .. 761 data size = 40 arrayBinary : 358 .. 449 arrayLinear : 379 .. 900 hashSet : 56 .. 83 treeSet : 357 .. 452 listBinary : 383 .. 475 data size = 50 arrayBinary : 385 .. 636 arrayLinear : 408 .. 516 hashSet : 46 .. 75 treeSet : 382 .. 780 listBinary : 376 .. 482 data size = 60 arrayBinary : 382 .. 636 arrayLinear : 451 .. 725 hashSet : 48 .. 67 treeSet : 372 .. 560 listBinary : 397 .. 554 data size = 70 arrayBinary : 395 .. 490 arrayLinear : 484 .. 574 hashSet : 51 .. 64 treeSet : 388 .. 701 listBinary : 418 .. 708 data size = 80 arrayBinary : 396 .. 599 arrayLinear : 511 .. 717 hashSet : 52 .. 117 treeSet : 404 .. 532 listBinary : 417 .. 861 data size = 90 arrayBinary : 411 .. 627 arrayLinear : 563 .. 853 hashSet : 55 .. 90 treeSet : 423 .. 642 listBinary : 446 .. 636 data size = 100 arrayBinary : 416 .. 621 arrayLinear : 582 .. 611 hashSet : 44 .. 55 treeSet : 364 .. 460 listBinary : 386 .. 897
ищем два миллиона неповторяющихся случайных целых чисел среди небольшого количества тоже случайных и тоже не повторяющихся (и тоже целых) чисел
замеряем лучший .. худший результат времени в миллисекундах для каждого из алгоритмов
замеряем лучший .. худший результат времени в миллисекундах для каждого из алгоритмов
search size = 2097151 data size = 10 arrayBinary : 30 .. 47 arrayLinear : 13 .. 27 hashSet : 13 .. 27 treeSet : 44 .. 63 listBinary : 43 .. 70 data size = 20 arrayBinary : 40 .. 51 arrayLinear : 26 .. 36 hashSet : 14 .. 19 treeSet : 60 .. 71 listBinary : 57 .. 77 data size = 30 arrayBinary : 50 .. 74 arrayLinear : 32 .. 58 hashSet : 12 .. 18 treeSet : 67 .. 81 listBinary : 71 .. 85 data size = 40 arrayBinary : 54 .. 69 arrayLinear : 44 .. 56 hashSet : 15 .. 21 treeSet : 75 .. 91 listBinary : 78 .. 91 data size = 50 arrayBinary : 54 .. 67 arrayLinear : 50 .. 64 hashSet : 11 .. 15 treeSet : 78 .. 93 listBinary : 79 .. 94 data size = 60 arrayBinary : 59 .. 70 arrayLinear : 62 .. 91 hashSet : 12 .. 18 treeSet : 85 .. 111 listBinary : 88 .. 101 data size = 70 arrayBinary : 59 .. 71 arrayLinear : 69 .. 84 hashSet : 14 .. 19 treeSet : 85 .. 101 listBinary : 86 .. 101 data size = 80 arrayBinary : 68 .. 83 arrayLinear : 81 .. 102 hashSet : 15 .. 24 treeSet : 90 .. 107 listBinary : 93 .. 110 data size = 90 arrayBinary : 77 .. 95 arrayLinear : 87 .. 108 hashSet : 17 .. 28 treeSet : 99 .. 118 listBinary : 115 .. 137 data size = 100 arrayBinary : 85 .. 108 arrayLinear : 95 .. 293 hashSet : 11 .. 16 treeSet : 104 .. 119 listBinary : 121 .. 152
import java.util.*; import java.util.function.*; import java.util.stream.*; public class SearchInts { private static final int times = Byte.MAX_VALUE; private static final int sizeSearch = Integer.MAX_VALUE / 1024; private static long time() { return System.currentTimeMillis(); } private static final Random random = new Random(); private static int[] randoms(final int size) { final Set<Integer> set = new HashSet<>(); while (set.size() < size) set.add(new Integer(random.nextInt())); final Integer[] integers = set.toArray(new Integer[]{}); final int[] xs = new int[size]; for (int x = 0; x < size; x++) xs[x] = integers[x].intValue(); return xs; } private static long arrayBinary(final int[] randoms, final int[] search) { final int[] xs = new int[randoms.length]; System.arraycopy(randoms, 0, xs, 0, randoms.length); final long start = time(); Arrays.sort(xs); for (final int x : search) Arrays.binarySearch(xs, x); return time() - start; } private static long arrayLinear(final int[] randoms, final int[] search) { final int[] xs = new int[randoms.length]; System.arraycopy(randoms, 0, xs, 0, randoms.length); final long start = time(); Arrays.sort(xs); for (final int x : search) for (final int xx : xs) if (xx == x) break; return time() - start; } private static long listBinary(final int[] randoms, final int[] search) { final List<Integer> xs = new ArrayList(randoms.length); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); Collections.sort(xs); for (final int x : search) Collections.binarySearch(xs, new Integer(x)); return time() - start; } private static long hashSet(final int[] randoms, final int[] search) { final Set<Integer> xs = new HashSet<>(); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); for (final int x : search) xs.contains(new Integer(x)); return time() - start; } private static long treeSet(final int[] randoms, final int[] search) { final Set<Integer> xs = new TreeSet<>(); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); for (final int x : search) xs.contains(new Integer(x)); return time() - start; } private static void test(final String name, final Supplier<Long> test) { final List<Long> results = Stream.generate(() -> test.get()) .limit(times).sorted().collect(Collectors.toList()); System.out.println(name + " : " + results.get(0) + " .. " + results.get(times - 1)); } public static void main(String[] args) { final int[] search = randoms(sizeSearch); System.out.println("search size = " + search.length); System.out.println(); Stream.iterate(10, x -> x + 10).limit(10).forEach(sizeData -> { final int[] randoms = randoms(sizeData); System.out.println("data size = " + randoms.length); test("arrayBinary", () -> arrayBinary(randoms, search)); test("arrayLinear", () -> arrayLinear(randoms, search)); test("hashSet ", () -> hashSet(randoms, search)); test("treeSet ", () -> treeSet(randoms, search)); test("listBinary ", () -> listBinary(randoms, search)); System.out.println(); }); } }
Amazing as expected
Oct. 22nd, 2016 12:36 amdata size = 2097151 search size = 32767 arrayBinary best 202 worst 621 hashSet best 1 worst 9 treeSet best 25 worst 60 listBinary best 803 worst 991
Ищем 30 тысяч случайных целых чисел в двух миллионах случайных целых чисел.
Замеряем лучшее и худшее время из 128 прогонов.
Множества (даже на дереве) как и ожидалось работают на несколько порядков лучше массивов. Список в аутсайдерах - это тоже немного удивительно, если учесть что список в данном случае построен на базе массивов - но результат в итоге принципиально другой. И привычный в последнее время результат - hash set просто абсолютно быстрый.
Самый главный вывод - с выходом JVM 1.6.23 произошла революция которую никто не заметил и которая называется escape analysis:
Escape analysis is supported and enabled by default in Java SE 6u23 and later.
Searches rates
Oct. 21st, 2016 11:19 pmprivate static long arrayBinary(final int[] randoms) { final int[] xs = new int[randoms.length]; System.arraycopy(randoms, 0, xs, 0, randoms.length); final long start = time(); Arrays.sort(xs); for (int x = 0; x < times; x++) Arrays.binarySearch(xs, x); return time() - start; } private static long arrayLinear(final int[] randoms) { final int[] xs = new int[randoms.length]; System.arraycopy(randoms, 0, xs, 0, randoms.length); final long start = time(); for (int x = 0; x < times; x++) for (final int xx : xs) if (x == xx) break; return time() - start; } private static long listBinary(final int[] randoms) { final List<Integer> xs = new ArrayList(randoms.length); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); Collections.sort(xs); for (int x = 0; x < times; x++) Collections.binarySearch(xs, new Integer(x)); return time() - start; } private static long listLinear(final int[] randoms) { final List<Integer> xs = new ArrayList(randoms.length); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); for (int x = 0; x < times; x++) xs.contains(new Integer(x)); return time() - start; } private static long hashSet(final int[] randoms) { final Set<Integer> xs = new HashSet<>(); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); for (int x = 0; x < times; x++) xs.contains(new Integer(x)); return time() - start; } private static long treeSet(final int[] randoms) { final Set<Integer> xs = new TreeSet<>(); for (final int x : randoms) xs.add(new Integer(x)); final long start = time(); for (int x = 0; x < times; x++) xs.contains(new Integer(x)); return time() - start; } size = 10 arrayBinary : 16 listBinary : 31 listLinear : 26 hashSet : 4 treeSet : 21 size = 20 arrayBinary : 18 listBinary : 33 listLinear : 50 hashSet : 4 treeSet : 33 size = 30 arrayBinary : 19 listBinary : 36 listLinear : 72 hashSet : 4 treeSet : 30 size = 40 arrayBinary : 25 listBinary : 44 listLinear : 97 hashSet : 4 treeSet : 32 size = 50 arrayBinary : 23 arrayLinear : 23 listBinary : 42 listLinear : 121 hashSet : 4 treeSet : 29 size = 60 arrayBinary : 27 listBinary : 48 listLinear : 147 hashSet : 4 treeSet : 36 size = 70 arrayBinary : 23 listBinary : 41 listLinear : 171 hashSet : 4 treeSet : 40 size = 80 arrayBinary : 24 listBinary : 45 listLinear : 190 hashSet : 4 treeSet : 44 size = 90 arrayBinary : 26 listBinary : 47 listLinear : 212 hashSet : 4 treeSet : 38 size = 100 arrayBinary : 27 listBinary : 48 listLinear : 239 hashSet : 4 treeSet : 46
Тенденции на первый взгляд примерно таковы:
Если вам нужно уложиться в менее чем 10 миллисекунд - используйте hash set. Важный момент это обеспечить скаляризацию посредством escape analysis (это собственно и есть главный пойнт исследования). TreeSet и бинарный поиск по ArrayList сопоставимы по скорости (и оба в два раза медленнее массивов - hash set же вообще просто вне конкуренции в любом случае). Интересно будет еще проверить не примитивные типы для данных - возможно картина изменится.
private static final int probes = Byte.MAX_VALUE; private static final int times = Integer.MAX_VALUE / 1024; private static long time() { return System.currentTimeMillis(); } private static final Random random = new Random(); private static int[] randoms(final int size) { final int[] xs = new int[size]; for (int x = 0; x < size; x++) xs[x] = random.nextInt(); return xs; } private static void arrayBinary(final int[] randoms) { final int size = randoms.length; final int[] xs = new int[size]; for (int x = 0; x < size; x++) xs[x] = randoms[x]; Arrays.sort(xs); for (int x = 0; x < times; x++) Arrays.binarySearch(xs, random.nextInt()); } private static void listBinary(final int[] randoms) { final List<Integer> xs = new ArrayList(randoms.length); for (final int x : randoms) xs.add(new Integer(x)); Collections.sort(xs); for (int x = 0; x < times; x++) Collections.binarySearch(xs, new Integer(random.nextInt())); } private static void listLinear(final int[] randoms) { final List<Integer> xs = new ArrayList(randoms.length); for (final int x : randoms) xs.add(new Integer(x)); for (int x = 0; x < times; x++) xs.contains(new Integer(random.nextInt())); } private static void hashSet(final int[] randoms) { final Set<Integer> xs = new HashSet<>(); for (final int x : randoms) xs.add(new Integer(x)); for (int x = 0; x < times; x++) xs.contains(new Integer(random.nextInt())); } private static long probe(final Runnable test) { final long start = time(); test.run(); return time() - start; } private static void test(final String name, final Runnable test) { Stream.generate(() -> probe(test)) .limit(probes).sorted().findFirst() .map(x -> name + " : " + x) .ifPresent(System.out::println); } public static void main(String[] args) { Stream.iterate(10, x -> x + 10).limit(10) .forEach(size -> { System.out.println("size = " + size); final int[] randoms = randoms(size); test("arrayBinary", () -> arrayBinary(randoms)); test("listBinary ", () -> listBinary(randoms)); test("listLinear ", () -> listLinear(randoms)); test("hashSet ", () -> hashSet(randoms)); System.out.println(); }); } size = 10 arrayBinary : 41 listBinary : 56 listLinear : 33 hashSet : 33 size = 20 arrayBinary : 51 listBinary : 69 listLinear : 58 hashSet : 31 size = 30 arrayBinary : 58 listBinary : 80 listLinear : 76 hashSet : 30 size = 40 arrayBinary : 67 listBinary : 89 listLinear : 100 hashSet : 32 size = 50 arrayBinary : 71 listBinary : 91 listLinear : 120 hashSet : 30 size = 60 arrayBinary : 78 listBinary : 103 listLinear : 145 hashSet : 30 size = 70 arrayBinary : 85 listBinary : 107 listLinear : 163 hashSet : 31 size = 80 arrayBinary : 84 listBinary : 109 listLinear : 194 hashSet : 32 size = 90 arrayBinary : 90 listBinary : 108 listLinear : 211 hashSet : 33 size = 100 arrayBinary : 90 listBinary : 113 listLinear : 239 hashSet : 29
Binary search vs HashSet
Oct. 19th, 2016 11:44 pmprivate static final int count = Integer.MAX_VALUE / 1024; private static long time() { return System.currentTimeMillis(); } private final static Random random = new Random(); private static void sortArray() { final int[] xs = new int[count]; for (int x = 0; x < count; x++) xs[x] = random.nextInt(); Arrays.sort(xs); for (int x = 0; x < count; x++) Arrays.binarySearch(xs, random.nextInt()); } private static void hashSet() { final Set<Integer> xs = new HashSet<>(); for (int x = 0; x < count; x++) xs.add(new Integer(random.nextInt())); for (int x = 0; x < count; x++) xs.contains(new Integer(random.nextInt())); } public static void main(String[] args) { sortArray(); hashSet(); { final long start = time(); sortArray(); final long time = time() - start; System.out.println("sort array: " + time); } { final long start = time(); hashSet(); final long time = time() - start; System.out.println("hash set: " + time); } } sort array: 1235 hash set: 735
HashSet почти в два раза быстрее чем "sort array then binary search"
Java escapes boxing int long
Oct. 18th, 2016 10:19 pmpublic class EscapeBoxing { private static final int fromInt = 128; private static final int toInt = Integer.MAX_VALUE; private static final long fromLong = 128; private static final long toLong = Integer.MAX_VALUE; private int xi; private long xl; private void set(final int x) { this.xi = x; } private void set(final long x) { this.xl = x; } private void setAny(final Object x) { if (x instanceof Long) set((Long) x); else if (x instanceof Integer) set((Integer) x); } private void testPrimInt() { for (int i = fromInt; i < toInt; i++) set(i); } private void testEscapeInt() { for (int i = fromInt; i < toInt; i++) setAny(new Integer(i)); } private void testBoxingInt() { for (int i = fromInt; i < toInt; i++) setAny(i); } private void testPrimLong() { for (long i = fromLong; i < toLong; i++) set(i); } private void testEscapeLong() { for (long i = fromLong; i < toLong; i++) setAny(new Long(i)); } private void testBoxingLong() { for (long i = fromLong; i < toLong; i++) setAny(i); } private static long time() { return System.currentTimeMillis(); } private static final int warm = 10; private void test() { for (int i = 0; i < warm; i++) { testPrimInt(); testEscapeInt(); testBoxingInt(); } { final long start = time(); testPrimInt(); final long time = time() - start; System.out.println("prim int: " + time); } { final long start = time(); testEscapeInt(); final long time = time() - start; System.out.println("escape int: " + time); } { final long start = time(); testBoxingInt(); final long time = time() - start; System.out.println("boxing int: " + time); } for (int i = 0; i < warm; i++) { testPrimLong(); testEscapeLong(); testBoxingLong(); } { final long start = time(); testPrimLong(); final long time = time() - start; System.out.println("prim long: " + time); } { final long start = time(); testEscapeLong(); final long time = time() - start; System.out.println("escape long: " + time); } { final long start = time(); testBoxingLong(); final long time = time() - start; System.out.println("boxing long: " + time); } } public static void main(String[] args) { new EscapeBoxing().test(); } } java version "1.8.0_102" Java(TM) SE Runtime Environment (build 1.8.0_102-b14) Java HotSpot(TM) 64-Bit Server VM (build 25.102-b14, mixed mode) prim int: 98 escape int: 96 boxing int: 91 prim long: 1900 escape long: 1909 boxing long: 2347
Как видим - escape analysis в JVM прекрасно работает даже в случае боксинга. Единственный тонкий момент - в боксинге используется кеширование обьектов для значений от -128 до 127 и в этом случае (для таких значений которые кешируются) ломается весь escape analysis поскольку закешированные значения уже как раз классифицируются как GlobalEscape обьекты и следовательно оптимизация к ним применяться не может а это в свою очередь отключает оптимизацию для всего метода (в этом случае). Однако если кеширование обьектов отключить (или вовсе не использовать боксинг а просто бесхитростно заворачивать всё в Integer - тогда вообще нет никаких проблем даже с числами в диапазоне -128..127) - всё прекрасно оптимизируется и нет никакой практически видимой разницы между примитивными и не-примитивными типами (особенно в случае int). Long же по сравнению с int к сожалению тормозит даже для примитивов - но и в этом случае escape analysis оптимизирует весьма и весьма хорошо.Возможно есть какой либо способ ускорять операции с long до уровня сопоставимого с int или когда нибудь в JVM таки оптимизируют long - но в данный момент пока еще все таки можно продолжать утверждать что JVM ориентируется именно на примитивный тип int и операции с int на порядок эффективнее чем с long. А вот с int/Integer в JVM всё просто замечательно :)
http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-enhancements-7.html#escapeAnalysis
Java monad (may be)
Oct. 14th, 2016 11:34 pminterface Kind<T extends Kind<T, A>, A> { interface Pointed<T extends Kind<T, A>, A> { T point(A a); } interface Functor<A, B, F extends Kind<F, A>, G extends Kind<G, B>> extends Pointed<F, A> { Function<F, G> map(Function<A, B> f); } interface Monad<A, B, F extends Kind<F, A>, G extends Kind<G, B>> extends Functor<A, B, F, G> { Function<F, G> bind(Function<A, G> f); } } interface Maybe<A> extends Kind<Maybe<A>, A> { static <A> Maybe<A> point(A a) { return a == null ? Nothing : new Just(a); } <B> Maybe<B> map(Function<A, B> f); <B> Maybe<B> bind(Function<A, Maybe<B>> f); Maybe Nothing = new Maybe() { @Override public Maybe map(final Function f) { return Nothing; } @Override public Maybe bind(final Function f) { return Nothing; } }; class Just<A> implements Maybe<A> { public A a; public Just(A a) { this.a = a; } @Override public <B> Maybe<B> map(final Function<A, B> f) { return point(f.apply(a)); } @Override public <B> Maybe<B> bind(final Function<A, Maybe<B>> f) { return f.apply(a); } } interface Monad<A, B> extends Kind.Monad<A, B, Maybe<A>, Maybe<B>> { } Monad monad = new Monad() { @Override public Function<Maybe, Maybe> bind(final Function f) { return m -> m.bind(f); } @Override public Function<Maybe, Maybe> map(final Function f) { return m -> m.map(f); } @Override public Maybe point(final Object o) { return Maybe.point(o); } }; static <A, B> Monad<A, B> monad() { return monad; } }