ハロプロソートのアルゴリズム比較

HPSortClassicMergeSort.ts

import HPSortBase, { HPSortProgress, HPSortResult } from './HPSortBase';

/**
 * HPSortMergeClassic is a class to emulate the sorting process in a classic manner (Simple two comparison merge sort)
 */
export default class HPSortClassicMergeSort<T> implements HPSortBase<T> {
  private targetSet: T[];

  private lstMember: number[][];
  private parent: number[];
  private rec: number[];
  private recIdx: number;
  private equal: (number | null)[];

  private idxLeft: number;
  private headLeft: number;
  private idxRight: number;
  private headRight: number;
  private numProgress: number;
  private numTotal: number;

  private numCompared: Readonly<number>;
  private isFinished: Readonly<boolean>;

  constructor(targetSet: T[]) {
    const lstMember: number[][] = [];
    const parent: number[] = [];
    let numTotal = 0;
    let n = 0;
    lstMember[n] = targetSet.map((_, i: number) => i);
    parent[n] = -1;
    n++;
    for (let i = 0; i < lstMember.length; i++) {
      if (lstMember[i].length >= 2) {
        const pivot = Math.ceil(lstMember[i].length / 2);
        lstMember[n] = lstMember[i].slice(0, pivot);
        numTotal += lstMember[n].length;
        parent[n] = i;
        n++;
        lstMember[n] = lstMember[i].slice(pivot, lstMember[i].length);
        numTotal += lstMember[n].length;
        parent[n] = i;
        n++;
      }
    }

    this.targetSet = targetSet;
    this.lstMember = lstMember;
    this.parent = parent;
    this.rec = targetSet.map((v) => 0);
    this.recIdx = 0;
    this.equal = targetSet.map((v) => null);

    this.idxLeft = lstMember.length - 2;
    this.idxRight = lstMember.length - 1;
    this.headLeft = 0;
    this.headRight = 0;
    this.numCompared = 0;
    this.numProgress = 0;
    this.numTotal = numTotal;
    this.isFinished = false;
  }

  public getComparable(): T[] | null {
    if (this.isFinished) {
      return null;
    }
    return [this.targetSet[this.getLeft()], this.targetSet[this.getRight()]];
  }

  private getLeft() {
    return this.lstMember[this.idxLeft][this.headLeft];
  }

  private getRight() {
    return this.lstMember[this.idxRight][this.headRight];
  }

  public get progress() {
    if (this.isFinished) {
      return 100;
    }
    return Math.floor((this.numProgress * 100) / this.numTotal);
  }

  select(...winnerIdx: number[]): void {
    if (winnerIdx.length === 2) {
      this.selectInternal('draw');
      return;
    } else if (winnerIdx.length === 1) {
      if (winnerIdx[0] === 0) {
        this.selectInternal('left');
        return;
      } else if (winnerIdx[0] === 1) {
        this.selectInternal('right');
        return;
      }
    } else if (winnerIdx.length === 0) {
      this.tie();
      return;
    }
    throw new Error('Invalid winnerIdx');
  }

  tie(): void {
    this.selectInternal('draw');
  }

  getNumCompared(): number {
    return this.numCompared;
  }
  getProgress(): HPSortProgress {
    return {
      numerator: this.numProgress,
      denominator: this.numTotal
    };
  }

  private selectInternal(flag: 'left' | 'right' | 'draw') {
    switch (flag) {
      case 'left':
        this.rec[this.recIdx] = this.getLeft();
        this.headLeft++;
        this.recIdx++;
        this.numProgress++;
        while (this.equal[this.rec[this.recIdx - 1]] !== null) {
          this.rec[this.recIdx] = this.getLeft();
          this.headLeft++;
          this.recIdx++;
          this.numProgress++;
        }
        break;
      case 'right':
        this.rec[this.recIdx] = this.getRight();
        this.headRight++;
        this.recIdx++;
        this.numProgress++;
        while (this.equal[this.rec[this.recIdx - 1]] !== null) {
          this.rec[this.recIdx] = this.getRight();
          this.headRight++;
          this.recIdx++;
          this.numProgress++;
        }
        break;
      case 'draw':
        this.rec[this.recIdx] = this.getLeft();
        this.headLeft++;
        this.recIdx++;
        this.numProgress++;
        while (this.equal[this.rec[this.recIdx - 1]] !== null) {
          this.rec[this.recIdx] = this.getLeft();
          this.headLeft++;
          this.recIdx++;
          this.numProgress++;
        }
        this.equal[this.rec[this.recIdx - 1]] = this.getRight();
        this.rec[this.recIdx] = this.getRight();
        this.headRight++;
        this.recIdx++;
        this.numProgress++;
        while (this.equal[this.rec[this.recIdx - 1]] !== null) {
          this.rec[this.recIdx] = this.getRight();
          this.headRight++;
          this.recIdx++;
          this.numProgress++;
        }
        break;
    }

    if (
      this.headLeft < this.lstMember[this.idxLeft].length &&
      this.headRight === this.lstMember[this.idxRight].length
    ) {
      // no more on right
      while (this.headLeft < this.lstMember[this.idxLeft].length) {
        this.rec[this.recIdx] = this.lstMember[this.idxLeft][this.headLeft];
        this.headLeft++;
        this.recIdx++;
        this.numProgress++;
      }
    } else if (
      this.headLeft === this.lstMember[this.idxLeft].length &&
      this.headRight < this.lstMember[this.idxRight].length
    ) {
      // no more on left
      while (this.headRight < this.lstMember[this.idxRight].length) {
        this.rec[this.recIdx] = this.lstMember[this.idxRight][this.headRight];
        this.headRight++;
        this.recIdx++;
        this.numProgress++;
      }
    }

    // if no more on both
    if (
      this.headLeft === this.lstMember[this.idxLeft].length &&
      this.headRight === this.lstMember[this.idxRight].length
    ) {
      for (let i = 0; i < this.lstMember[this.idxLeft].length + this.lstMember[this.idxRight].length; i++) {
        this.lstMember[this.parent[this.idxLeft]][i] = this.rec[i];
      }
      this.lstMember.pop();
      this.lstMember.pop();
      this.idxLeft = this.idxLeft - 2;
      this.idxRight = this.idxRight - 2;
      this.headLeft = 0;
      this.headRight = 0;

      this.rec = this.targetSet.map((v) => 0);
      this.recIdx = 0;
    }

    if (this.idxLeft < 0) {
      this.isFinished = true;
    }
    this.numCompared++;
  }

  public getResult(): HPSortResult<T> {
    const resultSet = this.targetSet.map((v, i) => {
      return {
        value: v,
        idx: i,
        rank: i + 1,
        score: (i + 1) * 3
      };
    });
    // if (!this.isFinished) {
    //   // for debugging purpose
    //   return resultSet;
    // }
    let numEquals = 0;
    let score = (resultSet.length - 1) * 3;
    for (let i = 0; i < resultSet.length; i++) {
      numEquals = 0;
      if (i < resultSet.length - 1) {
        for (let j = i; this.equal[this.lstMember[0][j]] === this.lstMember[0][j + 1]; j++) {
          numEquals++;
        }
      }
      resultSet[this.lstMember[0][i]].score = score - numEquals * 2;
      if (i < resultSet.length - 1) {
        for (let j = i; this.equal[this.lstMember[0][j]] === this.lstMember[0][j + 1]; j++) {
          i++;
          resultSet[this.lstMember[0][i]].score = score - numEquals * 2;
        }
      }
      score -= 3 * (numEquals + 1);
    }

    resultSet.sort((a, b) => {
      const diff = b.score - a.score;
      if (diff !== 0) {
        return diff;
      }
      return a.idx - b.idx;
    });

    for (let i = 0; i < resultSet.length; i++) {
      const ranking = i + 1;
      resultSet[i].rank = ranking;
      while (i < resultSet.length - 1 && resultSet[i].score === resultSet[i + 1].score) {
        i++;
        resultSet[i].rank = ranking;
      }
    }
    return resultSet;
  }
}

HPSortTopologicalSort.tsx

import HPSortBase, { HPSortProgress, HPSortResult } from './HPSortBase';

export interface HPSortTopologicalSortNode {
  getId(): string;
}

export default class HPSortTopologicalSort<T extends HPSortTopologicalSortNode> implements HPSortBase<T> {
  private list: T[];
  private map: Map<string, T>;
  private numCompared: number;
  private comparable: T[] | null = null;

  // a graph that maintains the comparison result. If a wins b, then we add an eddge from a to b
  private graph: Map<string, Set<string>>;
  // a set of pairs of which user select "tie"
  private ties: Map<string, Set<string>>;
  // record which ids are already compared yet
  private compared: Map<string, Set<string>>;

  constructor(list: T[]) {
    this.list = list;
    this.map = new Map(list.map((v) => [v.getId(), v]));
    this.graph = new Map(list.map((v) => [v.getId(), new Set<string>()]));
    this.ties = new Map(list.map((v) => [v.getId(), new Set<string>()]));
    this.compared = new Map(list.map((v) => [v.getId(), new Set<string>()]));
    this.numCompared = 0;
    this.updateComparable();
  }

  public select(...winnerIdx: number[]) {
    const comprable = this.comparable;
    if (comprable === null) {
      return;
    }
    const loserIdx = comprable.map((v, idx) => idx).filter((idx) => !winnerIdx.includes(idx));
    winnerIdx.forEach((widx) => {
      loserIdx.forEach((lidx) => {
        this.addEdge(comprable[widx], comprable[lidx]);
      });
    });
    this.numCompared++;
    this.updateComparable();
  }

  private addEdge(winner: T, loser: T) {
    if (this.graph.get(winner.getId())!.has(loser.getId())) {
      // already have winner => loser edge
      return;
    }
    this.graph.get(winner.getId())!.add(loser.getId());
    this.compared.get(winner.getId())!.add(loser.getId());
    this.compared.get(loser.getId())!.add(winner.getId());

    // all losers of loser is also a loser of winner.
    for (const loserOfLoser of this.graph.get(loser.getId())!) {
      this.addEdge(winner, this.map.get(loserOfLoser)!);
    }

    // all winners of winner is also a winner of loser.
    for (const winnerOfWinner of Array.from(this.graph.keys())) {
      if (this.graph.get(winnerOfWinner)!.has(winner.getId())) {
        this.addEdge(this.map.get(winnerOfWinner)!, loser);
      }
    }
  }

  public tie() {
    const comparable = this.comparable;
    if (comparable === null) {
      return;
    }
    for (const v1 of comparable) {
      for (const v2 of comparable) {
        if (v1.getId() !== v2.getId()) {
          this.ties.get(v1.getId())!.add(v2.getId());
          this.ties.get(v2.getId())!.add(v2.getId());
          this.compared.get(v1.getId())!.add(v2.getId());
          this.compared.get(v2.getId())!.add(v1.getId());
        }
      }
    }
    this.numCompared++;
    this.updateComparable();
  }

  public getComparable(): T[] | null {
    return this.comparable;
  }

  public getProgress(): HPSortProgress {
    let numerator = 0;
    let denominator = 0;
    for (const [, v] of this.compared.entries()) {
      denominator += this.list.length - 1; // total possible comparisons
      numerator += v.size; // already compared
    }
    return {
      numerator,
      denominator
    };
  }

  /**
   * getNumCompared returns the number of comparisons made so far.
   * @returns the number of comparisons made so far.
   */
  public getNumCompared(): number {
    return this.numCompared;
  }

  public getResult(): HPSortResult<T> {
    return this.topologicalSort().map((v, idx) => ({ value: v, rank: idx }));
  }

  /**
   * topologicalSort returns the sorted list of T based on the current comparison result.
   */
  private topologicalSort(): T[] {
    // we sort ids from the graph and ties, then generate T[] based on the sorted ids.
    const inDegree = new Map<string, number>();
    const result: string[] = [];
    const queue: string[] = [];

    for (const [node] of this.graph.entries()) {
      inDegree.set(node, 0);
    }
    for (const edges of this.graph.values()) {
      for (const edge of edges) {
        inDegree.set(edge, (inDegree.get(edge) || 0) + 1);
      }
    }

    for (const [node, degree] of inDegree.entries()) {
      if (degree === 0) queue.push(node);
    }

    while (queue.length > 0) {
      const node = queue.shift()!;
      result.push(node);

      for (const neighbor of this.graph.get(node)!) {
        inDegree.set(neighbor, inDegree.get(neighbor)! - 1);
        if (inDegree.get(neighbor) === 0) {
          queue.push(neighbor);
        }
      }
    }

    const finalResult = new Set<string>(result);
    for (const [node, ties] of this.ties.entries()) {
      if (finalResult.has(node)) {
        for (const tie of ties) {
          if (!finalResult.has(tie)) result.push(tie);
        }
      }
    }

    return result.map((id) => this.map.get(id)!);
  }

  private findUncompared(): T[] {
    const added = new Set<string>();
    const uncompared: T[] = [];
    for (const v1 of this.list) {
      if (added.has(v1.getId())) {
        continue;
      }
      if (this.compared.get(v1.getId())!.size < this.list.length - 1) {
        // v1 does not copmare with all other nodes
        if (uncompared.length > 0) {
          // if any of uncompared node has a comparison with v1, then we should not add v1 to the list.
          let shouldAdd = true;
          for (const v2 of uncompared) {
            if (this.compared.get(v1.getId())!.has(v2.getId()) || this.compared.get(v2.getId())!.has(v1.getId())) {
              shouldAdd = false;
            }
          }
          if (!shouldAdd) {
            continue;
          }
        }
        uncompared.push(v1);
        added.add(v1.getId());
        if (!added.has(v1.getId())) {
          if (uncompared.length >= 4) {
            return uncompared;
          }
        }

        for (const v2 of this.list) {
          if (v1.getId() === v2.getId()) {
            continue;
          }
          if (this.compared.get(v1.getId())!.has(v2.getId()) || this.compared.get(v2.getId())!.has(v1.getId())) {
            continue;
          }
          if (added.has(v2.getId())) {
            continue;
          }
          // v2 does not compare with v1, so add it.
          uncompared.push(v2);
          added.add(v2.getId());

          if (uncompared.length >= 4) {
            return uncompared;
          }
        }
      }
    }
    return uncompared;
  }

  private updateComparable() {
    const uncompared = this.findUncompared();
    if (uncompared.length <= 1) {
      this.comparable = null;
      return;
    }
    this.comparable = uncompared;
    return this.comparable;
  }
}