「線形探索」の版間の差分
表示
削除された内容 追加された内容
Add sample codes for C#, F#. |
m 誤字の修正。 |
||
(15人の利用者による、間の22版が非表示) | |||
1行目: | 1行目: | ||
{{pathnav|探索|frame=1}} |
{{pathnav|探索|frame=1}} |
||
'''線形探索'''(せんけいたんさく、{{lang-en-short|linear search, sequential search}})は、[[検索]]の[[アルゴリズム]]の一つ。 |
'''線形探索'''(せんけいたんさく、{{lang-en-short|linear search, sequential search}})は、[[検索]]の[[アルゴリズム]]の一つ。[[リスト (抽象データ型)|リスト]]や[[配列]]に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。 |
||
[[リスト]]や[[配列]]に入ったデータに対する検索を行うにあたって、 |
|||
先頭から順に比較を行い、それが見つかれば終了する。 |
|||
<math>n</math>個のデータから<math>m</math>個のデータを検索する場合、 |
<math>n</math>個のデータから<math>m</math>個のデータを検索する場合、時間計算量は <math>O(nm)</math> 、空間計算量は <math>O(1)</math> である。 |
||
時間計算量は<math>O(nm)</math>、空間計算量は<math>O(1)</math>必要となる。 |
|||
==アルゴリズムの流れ== |
==アルゴリズムの流れ== |
||
下のような7個のデータを持つリストがある |
下のような7個のデータを持つリストがある。 |
||
{|class=wikitable |
|||
|style="min-width:1.5em;text-align:center"|10 |
|||
{| border="1" |
|||
|style="min-width:1.5em;text-align:center"|7 |
|||
|- |
|||
|style="min-width:1.5em;text-align:center"|12 |
|||
|10||7||12||6||1||4||3 |
|||
|style="min-width:1.5em;text-align:center"|6 |
|||
|style="min-width:1.5em;text-align:center"|1 |
|||
|style="min-width:1.5em;text-align:center"|4 |
|||
|style="min-width:1.5em;text-align:center"|3 |
|||
|} |
|} |
||
線形探索では、 |
線形探索では、 |
||
*最初の要素である10を見る。 |
*最初の要素である10を見る。 |
||
*10は1ではないので、次の要素7を見る。 |
*10は1ではないので、次の要素7を見る。 |
||
22行目: | 21行目: | ||
*12は1ではないので、次の要素6を見る。 |
*12は1ではないので、次の要素6を見る。 |
||
*6は1ではないので、次の要素1を見る。1を見つけることができた。 |
*6は1ではないので、次の要素1を見る。1を見つけることができた。 |
||
なお、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。 |
|||
最悪のケースは、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。 |
|||
つまり、n個のデータから1個のデータを検索する場合に最悪<math>O(n)</math>の計算時間を要することとなる。 |
|||
==プログラム例== |
==プログラム例== |
||
=== |
===Common Lisp=== |
||
< |
<syntaxhighlight lang="lisp"> |
||
grep /REGEXP/, @list; |
|||
</source> |
|||
===[[Python]]=== |
|||
<source lang="python"> |
|||
def search(list, x): |
|||
return x in list |
|||
</source> |
|||
===[[Common Lisp]]=== |
|||
<source lang="lisp"> |
|||
(defun linear-search (list x) |
(defun linear-search (list x) |
||
( |
(dolist (e list) |
||
(when (equal e x) |
|||
(return-from linear-search T))) ;found |
|||
(or (zerop (- (car ls) x)) |
|||
NIL) ;not found |
|||
(spam (cdr ls)))))) |
|||
</syntaxhighlight> |
|||
(spam list))) |
|||
</source> |
|||
=== |
===F#=== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
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; |
|||
} |
|||
</source> |
|||
===[[F#]]=== |
|||
<source lang="fsharp"> |
|||
// For basic sequence: |
// For basic sequence: |
||
let find value (vs: seq<_>) = |
let find value (vs: seq<_>) = |
||
72行目: | 40行目: | ||
let rec ifind index = |
let rec ifind index = |
||
if e.MoveNext() then |
if e.MoveNext() then |
||
if e.Current = value then index else ifind (index + 1) |
if e.Current = value then Some index else ifind (index + 1) |
||
else |
else None |
||
ifind 0 |
ifind 0 |
||
79行目: | 47行目: | ||
let find2 value vl = |
let find2 value vl = |
||
let rec ifind2 index vl = |
let rec ifind2 index vl = |
||
if List.isEmpty vl then |
if List.isEmpty vl then None |
||
else if (List.head vl) = value then index |
else if (List.head vl) = value then Some index |
||
else ifind2 (index + 1) (List.tail vl) |
else ifind2 (index + 1) (List.tail vl) |
||
ifind2 0 vl |
ifind2 0 vl |
||
</syntaxhighlight> |
|||
</source> |
|||
===C=== |
|||
<syntaxhighlight lang="c"> |
|||
#include <stdio.h> |
|||
// 整数配列に対する線形探索関数 |
|||
int find(int array[], int array_size, int key) { |
|||
for (int i = 0; i < array_size; i++) { |
|||
if (array[i] == key) { |
|||
return i; // found |
|||
} |
|||
} |
|||
return -1; // not found |
|||
} |
|||
// 使用例 |
|||
int main(void) { |
|||
int list[10] = {12, 67, 87, 90, 125, 153, 214, 234, 653, 804}; |
|||
int result = find(list, sizeof list / sizeof *list, 90); |
|||
if (result < 0) { |
|||
printf("Not found.\n"); |
|||
} else { |
|||
printf("result = %d\n", result); |
|||
} |
|||
//=> result = 3 |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
===Haskell=== |
|||
<syntaxhighlight lang="haskell"> |
|||
-- 線形探索関数 |
|||
linearSearch :: Eq a => a -> [a] -> Maybe Int |
|||
linearSearch _ [] = Nothing |
|||
linearSearch x (y:ys) |
|||
| x == y = Just 0 |
|||
| otherwise = fmap (+1) (linearSearch x ys) |
|||
-- 使用例 |
|||
main = do |
|||
print $ linearSearch 3 [1, 2, 3, 4, 5] -- Just 2 |
|||
print $ linearSearch 6 [1, 2, 3, 4, 5] -- Nothing |
|||
</syntaxhighlight> |
|||
==関連項目== |
==関連項目== |
||
91行目: | 104行目: | ||
{{アルゴリズム}} |
{{アルゴリズム}} |
||
{{デフォルトソート:せんけいたんさく}} |
{{デフォルトソート:せんけいたんさく}} |
||
[[Category:検索アルゴリズム]] |
[[Category:検索アルゴリズム]] |
2024年6月22日 (土) 16:02時点における最新版
線形探索(せんけいたんさく、英: linear search, sequential search)は、検索のアルゴリズムの一つ。リストや配列に入ったデータに対する検索を行うにあたって、先頭から順に比較を行い、それが見つかれば終了する。
個のデータから個のデータを検索する場合、時間計算量は 、空間計算量は である。
アルゴリズムの流れ[ソースを編集]
下のような7個のデータを持つリストがある。
10 | 7 | 12 | 6 | 1 | 4 | 3 |
線形探索では、
- 最初の要素である10を見る。
- 10は1ではないので、次の要素7を見る。
- 7は1ではないので、次の要素12を見る。
- 12は1ではないので、次の要素6を見る。
- 6は1ではないので、次の要素1を見る。1を見つけることができた。
なお、このリストの場合、要素3を見つけるときで、7個のデータ全てを見ないと、見つけることができない。
プログラム例[ソースを編集]
Common Lisp[ソースを編集]
(defun linear-search (list x)
(dolist (e list)
(when (equal e x)
(return-from linear-search T))) ;found
NIL) ;not found
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[ソースを編集]
#include <stdio.h>
// 整数配列に対する線形探索関数
int find(int array[], int array_size, int key) {
for (int i = 0; i < array_size; i++) {
if (array[i] == key) {
return i; // found
}
}
return -1; // not found
}
// 使用例
int main(void) {
int list[10] = {12, 67, 87, 90, 125, 153, 214, 234, 653, 804};
int result = find(list, sizeof list / sizeof *list, 90);
if (result < 0) {
printf("Not found.\n");
} else {
printf("result = %d\n", result);
}
//=> result = 3
return 0;
}
Haskell[ソースを編集]
-- 線形探索関数
linearSearch :: Eq a => a -> [a] -> Maybe Int
linearSearch _ [] = Nothing
linearSearch x (y:ys)
| x == y = Just 0
| otherwise = fmap (+1) (linearSearch x ys)
-- 使用例
main = do
print $ linearSearch 3 [1, 2, 3, 4, 5] -- Just 2
print $ linearSearch 6 [1, 2, 3, 4, 5] -- Nothing