From 7a41749a49ff6a165011c5d3a73203b3a07be29c Mon Sep 17 00:00:00 2001 From: komutan Date: Tue, 7 Jul 2015 22:14:58 +0900 Subject: [PATCH] =?utf8?q?PriorityQueue=E3=82=92PairringHeap=E3=81=A7?= =?utf8?q?=E5=AE=9F=E8=A3=85=E3=80=82=E3=82=AD=E3=83=A5=E3=83=BC=E3=81=A8?= =?utf8?q?=E3=81=97=E3=81=A6=E3=81=AE=E9=A0=86=E5=BA=8F=E3=82=92=E7=A2=BA?= =?utf8?q?=E4=BF=9D=E3=80=82?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- src/LibNMeCab/Core/PriorityQueue.cs | 105 +++++++++++++------------- src/LibNMeCabTest/LibNMeCabTest.csproj | 6 +- src/LibNMeCabTest/PriorityQueueTest.cs | 131 +++++++++++++++++++++++++-------- 3 files changed, 155 insertions(+), 87 deletions(-) diff --git a/src/LibNMeCab/Core/PriorityQueue.cs b/src/LibNMeCab/Core/PriorityQueue.cs index 870e60c..be3cc43 100644 --- a/src/LibNMeCab/Core/PriorityQueue.cs +++ b/src/LibNMeCab/Core/PriorityQueue.cs @@ -7,77 +7,78 @@ namespace NMeCab.Core public class PriorityQueue where T : IComparable { - private readonly List heapList = new List(); - - public int Count + private class Node { - get { return this.heapList.Count; } + public T Value; + + public LinkedList Childs = new LinkedList(); + + public Node(T value) + { + this.Value = value; + } } + private Node rootNode = null; + + public int Count { get; private set; } + + public T First { get { return this.rootNode.Value; } } + public void Clear() { - this.heapList.Clear(); + this.rootNode = null; + this.Count = 0; + } + + public void RemoveFirst() + { + this.rootNode = this.Unify(this.rootNode.Childs); + this.Count--; } public void Push(T item) { - if (item == null) throw new ArgumentNullException("item"); + this.rootNode = this.Merge(this.rootNode, new Node(item)); + this.Count++; + } - //up heap - int currentPos = this.heapList.Count; //tail - this.heapList.Add(default(T)); - while (currentPos != 0) - { - int parentPos = (currentPos - 1) / 2; - T parent = this.heapList[parentPos]; + public T Pop() + { + T ret = this.First; + this.RemoveFirst(); + return ret; + } - if (parent.CompareTo(item) <= 0) break; + private Node Merge(Node l, Node r) + { + if (l == null) return r; + if (r == null) return l; - this.heapList[currentPos] = parent; //down - currentPos = parentPos; + if (l.Value.CompareTo(r.Value) > 0) + { + r.Childs.AddFirst(l); + return r; + } + else + { + l.Childs.AddLast(r); + return l; } - this.heapList[currentPos] = item; //commit } - public T Pop() + private Node Unify(LinkedList nodes) { - if (this.heapList.Count == 0) throw new InvalidOperationException("Empty"); + if (nodes == null || nodes.Count == 0) return null; - T root = this.heapList[0]; + Node x = nodes.First.Value; + nodes.RemoveFirst(); + if (nodes.Count == 0) return x; - int tailPos = this.heapList.Count - 1; - if (tailPos != 0) - { - //down heap - T tail = this.heapList[tailPos]; - int currentPos = 0; - while (true) - { - int childPos = currentPos * 2 + 1; //left child - if (childPos >= tailPos) break; - T child = this.heapList[childPos]; - - int rChiledPos = childPos + 1; //right child - if (rChiledPos < tailPos) - { - T rChiled = this.heapList[rChiledPos]; - if (child.CompareTo(rChiled) > 0) - { - child = rChiled; - childPos = rChiledPos; - } - } - - if (tail.CompareTo(child) < 0) break; - - this.heapList[currentPos] = child; //up - currentPos = childPos; - } - this.heapList[currentPos] = tail; //commit - } - this.heapList.RemoveAt(tailPos); + Node y = nodes.First.Value; + nodes.RemoveFirst(); - return root; + return this.Merge(this.Merge(x, y), this.Unify(nodes)); } } } diff --git a/src/LibNMeCabTest/LibNMeCabTest.csproj b/src/LibNMeCabTest/LibNMeCabTest.csproj index b60dc79..9d03d55 100644 --- a/src/LibNMeCabTest/LibNMeCabTest.csproj +++ b/src/LibNMeCabTest/LibNMeCabTest.csproj @@ -57,9 +57,9 @@ - - {4ffe4221-2f41-446e-be59-d9cfcdf91ac6} - LibNMeCab35 + + {86711194-4c2b-4853-830f-07c57f035283} + LibNMeCab40MMF diff --git a/src/LibNMeCabTest/PriorityQueueTest.cs b/src/LibNMeCabTest/PriorityQueueTest.cs index baf3b5b..aa3a6c9 100644 --- a/src/LibNMeCabTest/PriorityQueueTest.cs +++ b/src/LibNMeCabTest/PriorityQueueTest.cs @@ -1,92 +1,159 @@ using System; using Microsoft.VisualStudio.TestTools.UnitTesting; +using System.Collections.Generic; +using System.Linq; +using System.Diagnostics; namespace LibNMeCabTest { + public class Element : IComparable + { + public int Priority { get; set; } + + public int Order { get; set; } + + public int CompareTo(Element other) + { + return this.Priority.CompareTo(other.Priority); + } + + public override int GetHashCode() + { + return this.Priority; + } + + public override bool Equals(object obj) + { + var other = obj as Element; + return other != null + && this.Priority == other.Priority + && this.Order == other.Order; + } + + public override string ToString() + { + return "priority:" + this.Priority + " order:" + this.Order; + } + } + [TestClass] public class PriorityQueueTest { [TestMethod] public void TestMethod1() { - var target = new NMeCab.Core.PriorityQueue(); + var queue = new NMeCab.Core.PriorityQueue(); + var collection = new List(); var count = 0; - for (int i = 0; i < 10; i++) + for (int i = 0; i < 2; i++) { - for (int j = 0; j < 10; j++) + //追加 優先度昇順 + for (int j = 0; j < 3; j++) { - target.Push(j); + var item = new Element { Priority = j, Order = count }; + queue.Push(item); + collection.Add(item); count++; - Assert.AreEqual(target.Count, count); + Assert.AreEqual(queue.Count, count); } } - int wrk1 = 0; - for (int k = 0; k < count; k++) + //並べ直し + collection = (from e in collection + orderby e.Priority, e.Order + select e).ToList(); + + //取り出し + foreach (var expected in collection) { - int wrk2 = target.Pop(); + var actual = queue.Pop(); count--; - Assert.AreEqual(target.Count, count); - Assert.IsTrue(wrk1 <= wrk2); - wrk1 = wrk2; + + Assert.AreEqual(expected, actual); + Assert.AreEqual(count, queue.Count); } } [TestMethod] public void TestMethod2() { - var target = new NMeCab.Core.PriorityQueue(); + var queue = new NMeCab.Core.PriorityQueue(); + var collection = new List(); var count = 0; - for (int i = 0; i < 10; i++) + for (int i = 0; i < 2; i++) { - for (int j = 10; j >= 0; j--) + //追加 優先度降順 + for (int j = 3; j >= 0; j--) { - target.Push(j); + var item = new Element { Priority = j, Order = count }; + queue.Push(item); + collection.Add(item); count++; - Assert.AreEqual(target.Count, count); + + Assert.AreEqual(count, queue.Count); } } - int wrk1 = 0; - for (int k = 0; k < count; k++) + //並べ直し + collection = (from e in collection + orderby e.Priority, e.Order + select e).ToList(); + + //取り出し + foreach (var expected in collection) { - int wrk2 = target.Pop(); + var actual = queue.Pop(); count--; - Assert.AreEqual(target.Count, count); - Assert.IsTrue(wrk1 <= wrk2); - wrk1 = wrk2; + + Assert.AreEqual(expected, actual); + Assert.AreEqual(count, queue.Count); } } [TestMethod] public void TestMethod3() { - var target = new NMeCab.Core.PriorityQueue(); + var queue = new NMeCab.Core.PriorityQueue(); + var collection = new List(); + var order = 0; var count = 0; var rnd = new Random(); + //追加と取り出しを一定数繰り返す for (int i = 0; i < 1000; i++) { + //ランダム優先度でランダム個追加 int repeat = rnd.Next(10); for (int j = 0; j < repeat; j++) { - target.Push(rnd.Next(10)); + var item = new Element { Priority = rnd.Next(10), Order = order }; + collection.Add(item); + queue.Push(item); + order++; count++; - Assert.AreEqual(target.Count, count); + + Assert.AreEqual(count, queue.Count); } - repeat = rnd.Next(target.Count); - int wrk1 = 0; - for (int k = 0; k < repeat; k++) + //並べ直し + collection = (from e in collection + orderby e.Priority, e.Order + select e).ToList(); + + //ランダム個取り出し + repeat = rnd.Next(collection.Count); + for (int j = 0; j < repeat; j++) { - int wrk2 = target.Pop(); + var actual = queue.Pop(); + var expected = collection[j]; count--; - Assert.AreEqual(target.Count, count); - Assert.IsTrue(wrk1 <= wrk2); - wrk1 = wrk2; + + Assert.AreEqual(expected, actual); + Assert.AreEqual(count, queue.Count); } + collection.RemoveRange(0, repeat); } } } -- 2.11.0