「線形探索」の版間の差分
表示
削除された内容 追加された内容
Improvement F# codes. |
→プログラム例: アルゴリズムの説明に全くなっていないPerlとPythonの例を除去。あと「見出しをリンクにしない」 |
||
27行目: | 27行目: | ||
==プログラム例== |
==プログラム例== |
||
=== |
===Common Lisp=== |
||
<source lang="perl"> |
|||
grep /REGEXP/, @list; |
|||
</source> |
|||
===[[Python]]=== |
|||
<source lang="python"> |
|||
def search(list, x): |
|||
return x in list |
|||
</source> |
|||
===[[Common Lisp]]=== |
|||
<source lang="lisp"> |
<source lang="lisp"> |
||
(defun linear-search (list x) |
(defun linear-search (list x) |
||
48行目: | 37行目: | ||
</source> |
</source> |
||
=== |
===C#=== |
||
<source lang="csharp"> |
<source lang="csharp"> |
||
public static int Find<T>(this IEnumerable<T> enumerable, T value) |
public static int Find<T>(this IEnumerable<T> enumerable, T value) |
||
65行目: | 54行目: | ||
</source> |
</source> |
||
=== |
===F#=== |
||
<source lang="fsharp"> |
<source lang="fsharp"> |
||
// For basic sequence: |
// For basic sequence: |
||
85行目: | 74行目: | ||
</source> |
</source> |
||
=== |
===C=== |
||
<source lang="c"> |
<source lang="c"> |
||
/* for integer array: */ |
/* for integer array: */ |
2017年2月19日 (日) 01:54時点における版
線形探索(せんけいたんさく、英: linear search, sequential search)は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。
個のデータから個のデータを検索する場合、 時間計算量は、空間計算量は必要となる。
アルゴリズムの流れ
下のような7個のデータを持つリストがある。このときに今要素1がどこにあるか、検索したい。
10 | 7 | 12 | 6 | 1 | 4 | 3 |
線形探索では、
- 最初の要素である10を見る。
- 10は1ではないので、次の要素7を見る。
- 7は1ではないので、次の要素12を見る。
- 12は1ではないので、次の要素6を見る。
- 6は1ではないので、次の要素1を見る。1を見つけることができた。
最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。 つまり、n個のデータから1個のデータを検索する場合に最悪の計算時間を要することとなる。
プログラム例
Common Lisp
(defun linear-search (list x)
(labels ((spam (ls)
(and (consp ls)
(or (zerop (- (car ls) x))
(spam (cdr ls))))))
(spam list)))
C#
public static int Find<T>(this IEnumerable<T> enumerable, T value)
{
var index = 0;
foreach (var v in enumerable)
{
if (v == value)
{
return index;
}
index++;
}
return -1;
}
F#
// For basic sequence:
let find value (vs: seq<_>) =
use e = vs.GetEnumerator()
let rec ifind index =
if e.MoveNext() then
if e.Current = value then Some index else ifind (index + 1)
else None
ifind 0
// For list:
let find2 value vl =
let rec ifind2 index vl =
if List.isEmpty vl then None
else if (List.head vl) = value then Some index
else ifind2 (index + 1) (List.tail vl)
ifind2 0 vl
C
/* for integer array: */
int
find(
int array[],
int array_size,
int value)
{
int i;
for (i = 0; i < array_size; ++i)
{
if (array[i] == value) { return i; }
}
return -1;
}