前Kの大きいO(N)アルゴリズムを探して、千万の中で前1000のデータを探して300ミリ秒未満です.
19549 ワード
適当に書くと、速度が一番ではないかもしれませんが、もうO(n)です.実際に使用する場合は、シミュレーションデータである他のデバイスやプログラムの出力速度に制限される場合があります.
構想は前Kの大きい秩序を維持して、それから挿入する時判断して、大きく挿入しないで、しかも挿入する時2分で位置を探して、最後の1つを弾きます.
後で時間があってから一番たくさんの挿入と維持を検討して、これはまずここに置いておきましょう.N*(LogK+C)は定数*Nであるため、複雑度は依然としてO(N)であると考える.
構想は前Kの大きい秩序を維持して、それから挿入する時判断して、大きく挿入しないで、しかも挿入する時2分で位置を探して、最後の1つを弾きます.
後で時間があってから一番たくさんの挿入と維持を検討して、これはまずここに置いておきましょう.N*(LogK+C)は定数*Nであるため、複雑度は依然としてO(N)であると考える.
using
System;
using
System.Collections.Generic;
using
System.Linq;
using
System.Text;
using
System.Diagnostics;
namespace
ConsoleApplication5
{
class
Program
{
static
void
Main(
string
[] args)
{
MaxHeap
<
KV
>
myKV
=
new
MaxHeap
<
KV
>
(
1000
);
Random Rand
=
new
Random();
Stopwatch sw
=
new
Stopwatch();
sw.Start();
for
(
int
i
=
0
; i
<
1000
*
1000
; i
++
)
{
KV iterm
=
new
KV(i.ToString(), Rand.Next(
1000
));
//
Console.WriteLine(" " + (i + 1) + " ：“" + iterm.Key + "”," + iterm.Value);
myKV.Insert(iterm);
}
sw.Stop();
//
Show(myKV);
Console.WriteLine(sw.ElapsedMilliseconds);
Console.Read();
}
static
void
Show(MaxHeap
<
KV
>
heap)
{
for
(
int
i
=
0
; i
<
heap.Heap.Length; i
++
)
{
KV iterm
=
heap.Heap[i];
string
result
=
(iterm
==
null
)
?
"
Null
"
:
"
\"
"
+
iterm.Key
+
"
\",
"
+
iterm.Value;
Console.WriteLine(result);
}
Console.WriteLine(
"
：
"
+
heap.Count
+
"
-------------------------------
"
);
}
public
class
KV : IComparable
<
KV
>
{
public
string
Key;
public
int
Value;
public
KV(
string
key,
int
value)
{
Key
=
key;
Value
=
value;
}
public
int
CompareTo(KV x)
{
if
(x
==
null
)
{
return
1
;
}
if
(
this
.Value
==
x.Value)
{
return
this
.Key.CompareTo(x.Key);
}
else
{
return
this
.Value.CompareTo(x.Value);
}
}
}
public
class
MaxHeap
<
T
>
where
T : IComparable
<
T
>
{
private
int
heapSize
=
0
;
public
T[] Heap;
public
int
Count
=
0
;
public
MaxHeap(
int
size)
{
heapSize
=
size;
Heap
=
new
T[size];
}
public
void
Insert(T iterm)
{
if
(iterm.CompareTo(Heap[heapSize
-
1
])
>
0
)
{
Insert(iterm,
0
, (Heap.Length
-
1
)
/
2
, Heap.Length
-
1
);
}
Count
++
;
}
private
void
Insert(T iterm,
int
min,
int
pos,
int
max)
{
if
((iterm.CompareTo(Heap[pos])
<=
0
&&
iterm.CompareTo(Heap[pos
+
1
])
>=
0
)
||
pos
==
0
)
{
for
(
int
i
=
heapSize
-
1
; i
>
pos; i
--
)
{
Heap[i]
=
Heap[i
-
1
];
}
if
(pos
==
0
)
{
Heap[pos]
=
iterm;
}
else
{
Heap[pos
+
1
]
=
iterm;
}
}
else
{
if
(iterm.CompareTo(Heap[pos])
>
0
)
{
max
=
pos;
}
else
{
min
=
pos;
}
pos
=
Convert.ToInt32((max
+
min)
/
2
);
Insert(iterm, min, pos, max);
}
}
}
}
}