O(n) ではなく O(1) のリスト (10,000,000 オーダーで非常に大きなもの) に要素が存在するかどうかを確認したい。take O(n) を使用したリストだelem x ysから、別のデータ型/コンストラクターを使用したいのですが、それはPrelude(配列ではなく) にある必要があります。助言がありますか？また、データ型を作成する必要がある場合、どのようなものになるでしょうか?
また、数字の大きなリストを同じ順序 (10,000,000) で並べ替え、可能な限り短い時間で要素にインデックスを付けます。
O（1）時間でデータセット内のアイテムを検索する唯一の方法は、そのアイテムがどこにあるかをすでに知っている場合ですが、その場合は検索する必要はありません。ソートされていないデータの場合、検索はO（n）時間です。ソートされたデータの場合、検索はO（log n）時間です。
Bloom フィルターまたはHashtableのいずれかを使用する必要があります。どちらもプレリュードにはありません。さらに、どちらも Array が利用可能であることに依存しています。
残っている唯一のオプションは、ある種のツリーです。heapをお勧めします。実装は難しくなく、無料で並べ替えもできます。
更新: おっと! ヒープがルックアップを提供しないことを忘れていました。BSTはあなたの選択です。