JavaScriptでチェーン操作を実現-08 Remove Dupliccates

TL;DR
順序付けされたチェーンの重さを消すためには、長いチェーンテーブルを考慮して、最後の最適化を呼び出す必要があります.シリーズの目次は前文と目次に会ってください.
需要removeDuplicates()関数を実現し、昇順に並べられたチェーンテーブルを与え、チェーンテーブルの重複要素を除去し、修正されたチェーンテーブルを返します.理想的な場合はチェーンは一度回るべきです.

var list = 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null
removeDuplicates(list) === 1 -> 2 -> 3 -> 4 -> 5 -> null

着信チェーンがnullならnullに戻る.
この解決策はチェーンが長い場合、再帰的にスタックがオーバーフローすることを考慮する必要がありますので、再帰的なスキームは最終再帰的なものを使用しなければなりません.
紙面の制限のため、ここでは何が最終的に再帰するのかを説明していません.詳しく知りたいのは、まず最後の呼出の定義を見てみてもいいです.
再帰的なバージョン-非再帰的なバージョン
配列やチェーンに対して重さを除去すること自体は多くの種類のアルゴリズムですが、もしチェーンテーブルが順序付けられているならば、解法は単一で多くなります.重複する要素は全部隣接しています.a -> a1 -> a2 ... aN -> bと仮定すると、a1からaNまでがaに対する繰り返しである場合、デバックはチェーンをa -> bに変えることである.
再帰的なバージョンがループされていないので、再帰的な動作は、第1回の除去a1、第2回の除去a2のような重複要素を1つしか引かない.
まず簡単な再帰バージョンを見て、このバージョンはremoveDuplicates自身に再帰される.最初にチェーンテーブルのヘッダノードheadを取り出し、その後のノードと重複していることが発見されたら、headにその後のノードを指すようにし(重複を差し引いて)、次にheadを次の再帰的に入れる.重複がない場合は、headの次のノードに再帰し、結果をhead.nextに向ける.

function removeDuplicates(head) {
  if (!head) return null

  const nextNode = head.next
  if (nextNode && head.data === nextNode.data) {
    head.next = nextNode.next
    return removeDuplicates(head)
  }

  head.next = removeDuplicates(nextNode)
  return head
}

このバージョンは最初のreturn removeDuplicates(head)だけで最終的なreturn headではない.この解法は完全な最終再帰とは言えないが、性能は悪いとは言えない.私がテストしたら30000個のノードのチェーンテーブルを処理できますが、400個は必ずスタックにオーバーフローします.
再帰的なバージョン-最後の再帰的なバージョン
多くの再帰が仕方なく自然に最後まで書いて再帰します.本質的な原因は再帰過程で共有変数を維持できないことです.これも循環の利点です.上記の例のhead.next = removeDuplicates(nextNode)は典型的なもので、headを保持したいです.幸い、再帰的に結果をhead.nextに与えます.最後の再帰的最適化の基本的な考え方は、共有変数を次の再帰的プロセスに伝え続けることであり、このようなやり方は往々にして付加的な関数パラメータを用いる必要がある.以下は変更後の最終再帰版である.

function removeDuplicatesV2(head, prev = null, re = null) {
  if (!head) return re

  re = re || head
  if (prev && prev.data === head.data) {
    prev.next = head.next
  } else {
    prev = head
  }

  return removeDuplicatesV2(head.next, prev, re)
}

私たちは2つの変数prevとreを追加しました.prevは、headの前のノードを表し、再帰の過程でprevとheadが重複しているかどうかを判断する.最後にチェーンテーブルのヘッダを返すためにreというパラメータを加えました.最後の戻り値です.reは、最初のhead、すなわち、最初に再帰されたチェーンの頭だけを指す.このアルゴリズムはチェーンテーブル自体を修正するので、チェーンテーブルが空でない限り、リターン値として先頭に重複があっても、取り外されたのはヘッドノードの後のノードです.
どうやってテストしますか?
まず、私たちは後戻り最適化をサポートする環境が必要です.私がテストした環境はNode v 7です.Nodeは6.2の後に後戻り最適化をサポートするはずですが、harmony_tailcallsパラメータのオープンを指定する必要があります.デフォルトは起動しません.私が使っているMochaでテストを書いていますので、パラメータをmocha.optsに書いてください.構成は以下の通りです.

--use_strict
--harmony_tailcalls
--require test/support/expect.js

次に私達は長い時間を生成する方法が必要です.ランダムに繰り返して、生順に並べられたチェーン表です.私の書き方は以下の通りです.

// Usage: buildRandomSortedList(40000)
function buildRandomSortedList(len) {
  let list
  let prevNode
  let num = 1

  for (let i = 0; i < len; i++) {
    const node = new Node(randomBool() ? num++ : num)
    if (!list) {
      list = node
    } else {
      prevNode.next = node
    }
    prevNode = node
  }

  return list
}

function randomBool() {
  return Math.random() >= 0.5
}

その後、テストができます.オーバーフローとオーバーフローがない場合を同時にテストするために、helperを書いてください.このhelperの簡単な判定関数はRangeErrorから投げ出されていますか?関数の論理は前のテストで保証されていますので、ここでは結果が正しいかどうかをテストしません.

function createLargeListTests(fn, { isOverflow }) {
  describe(`${fn.name} - max stack size exceed test`, () => {
    it(`${isOverflow ? 'should NOT' : 'should'} be able to handle a big random list.`, () => {
      Error.stackTraceLimit = 10

      expect(() => {
        fn(buildRandomSortedList(40000))
      })[isOverflow ? 'toThrow' : 'toNotThrow'](RangeError, 'Maximum call stack size exceeded')
    })
  })
}

createLargeListTests(removeDuplicates, { isOverflow: true })
createLargeListTests(removeDuplicatesV2, { isOverflow: false })

完全なテストはGitHubを見ました.
ちなみに、以上の二つの再帰案はCodewars上でスタックオーバーします.これはCodewarsはNode v 6を使っていますが、最終的な再帰的最適化は開かれていません.
サイクルバージョン
構想が一致しているなら、詳細に説明しなくてもいいです.直接コードを見ます.

function removeDuplicatesV3(head) {
  for (let node = head; node; node = node.next) {
    while (node.next && node.data === node.next.data) node.next = node.next.next
  }
  return head
}

循環体の外部における共有変数nodeおよびheadのために、この例コードは再帰バージョンよりも簡単に直観されることが多い.
締め括りをつける
循環と再帰のどちらが優れていますか?どちらが悪いですか?それぞれ適当な場所があります.このkataはリサイクルが簡単な例です.また、中間変数を伝達するためには、通常の再帰的な考え方ではなく、書いた感じがよく似ています.これはなぜ私がほとんどのkataに対して最終的な再帰をしていないのですか?この教程の目的は再帰的な考え方を示すことです.
アルゴリズムに関するコードとテストは全部GitHubに置いています.もしあなたに助けがあれば、いい評価をお願いします.
参考資料
Codewars Kata GitHubのコードはGitHubのテストを実現します.