arrays - ソートされていない配列に要素が存在するかどうかを確認する最速の方法は?

Question

要素線形検索でソートされていない配列を検索するための最速のアルゴリズムは? つまり、マージソートとバイナリ検索の組み合わせは遅くなると思います。他のオプションはありますか？(マルチスレッドを含まないアルゴリズムに関して)?

Answer 1

はい、配列がソートされておらず、その構造について知っているのはそれだけの場合、要素を検索する最速の方法は、線形時間O(n)かかるすべての要素を考慮することです。

配列を頻繁に検索する場合は、最初の並べ替えを検討してから、正しい並べ替えられたインデックスに要素を挿入することをお勧めします (バイナリ検索を使用)。これは、最初の並べ替えがO(n log n)であることを意味しますが、各挿入と検索にはO(log n)が必要です。トレードオフと、それがO(1)挿入およびO(n)検索よりも優れているかどうかがすべてです。

マルチスレッドはないと言いましたが、それはパフォーマンスを向上させる簡単な方法であり、複数のスレッドがリスト内の異なるチャンクを参照するようにします。

Answer 2

ソートされていない配列内の要素を検索するメソッドを作成しました。

#include <iostream> 
#include <vector> // for 2D vector 
#include<bits/stdc++.h>
using namespace std; 

int main() 
{ 
    vector<vector<int>> vect{ {0},{0},{0},{0},{0},{0},{0},{0},{0},{0} }; 
    int count[10];
    int min = INT_MAX; 
    int max = INT_MIN;   
    for (int i = 0; i < 10; i++)
    {
        count[i] = 0;
    }

    for (int i = 0; i < 7; i++)
    {
        //input 7 integers
        int ip,
            rem;
        cin >> ip;
        rem = ip % 10;
        if (ip > max)
            max = ip;
        if (min > ip)
            min = ip;
        if (vect[rem][0] == 0 && count[rem] == 0)
        {
            vect[rem][0] = ip;
            count[rem]++;
        }
        else
        {
            vect[rem].push_back(ip);
            count[rem]++;
        }
    }

    int find;
int flag = 0;
    cin >> find;
    int rem = find % 10;
    if (find>max || find<min || count[rem] == 0)
        cout<<"not present in the array";
    else
    {
        for (int i = 0; i < vect[rem].size(); i++)
        {
            if (vect[rem][i] == find)
            {
                cout << "found";flag = 1;
                break;
            }
        }
      if(flag == 0)
        cout<<"not present in the array";
    }

    return 0; 
}

私はこれがより速くなることがわかります。基本的に、要素を受け取ったら 2D ベクトルに格納します。

残りの数値 (数値 % 10) をベクトルのインデックスとして取得し、それらの要素をプッシュします。要素を検索するために、ベクトルの特定のインデックスに存在する要素のみをトラバースしています。
このように、比較の数は少なくなります。