0xDEADBEEF

RSS odkazy english edition

multi intersection

struct Conj {
  uint[][] arrays;
  uint[] positions;
  bool finished = false;

  enum sentinel = uint.max;

  uint next() {
    if (finished) return sentinel;

    uint max = arrays[0][positions[0]];

    for (int i = 0; i < arrays.length; i++) {
      auto arr = arrays[i];
      auto pos = positions[i];

      while (true) {
        auto current = arr[pos];
        if (current > max) {
          max = current;
          i = -1;
          break;

        } else if (current < max) {
          pos++;
          positions[i] = pos;

          if (pos >= arr.length) {
            finished = true;
            return sentinel;
          }

        } else if (current == max) {
          break;
        }
      }
    }

    movePositions();
    return max;
  }

  void movePositions() {
    foreach (i, ref pos; positions) {
      pos++;
      if (pos >= arrays[i].length) {
        finished = true;
      }
    }
  }
}

benchmarking code

import std.algorithm;
import std.random;
import std.range;
import std.stdio;
import std.datetime.stopwatch;

void main() {
  auto rnd = Xorshift(47);

  uint[][] arrays =
    sequence!((_, i) =>
      randomSample(iota(uint(0), uint(1_000_000)), uniform(540_000, 900_000, rnd), rnd).array
    ).take(10).array;

  sort!((a, b) => a.length < b.length)(arrays);

  foreach (arr; arrays) {
    assert(isStrictlyMonotonic(arr));
  }

  foreach (i; 0 .. 100) {
    auto conj = Conj(arrays, new uint[arrays.length]);
    auto timer = StopWatch(AutoStart.yes);
    ulong sink, count;
    while (!conj.finished) {
      sink += conj.next();
      count++;
    }
    writeln(sink, " ", count);
    writeln("time ", timer.peek.total!"usecs", " us");
  }

  auto a = arrays;
  writeln(setIntersection(a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]).count);
}
píše k47 (@kaja47, k47)