0

以下に説明する場合、どのデータ構造を使用する必要がありますか。

私は単純な豆を持っています： 

 public class Points { 

    private String name; 
    private String address; 
    private int phone; 
    private int coord1; 
    private int coord2; 

    //getters+setters 

    }

いくつかのBeanを作成し、それらをある種のデータ構造に格納したいと思います。また、名前と住所の2つのパラメータで検索できます。

たとえば、ユーザーが「7」と入力すると、いくつかのオブジェクトが返されます。この文字が含まれている名前またはアドレスはどれですか。

どのデータ構造を使用する必要があり、どのように検索しますか？

重要な場合は、Androidアプリに実装するためにこれが実際に必要です。マップ上のポイントを検索したいと思います。また、データベースは20個しかないため、これまで作成したくありません。

事前にどうもありがとうございました。

4

2 に答える 2

1

ハッシュマップなどのJavaのコレクションを試してください。これをPCで実行しましたが、10000アイテムの場合、検索で3440の結果が返され、76ミリ秒かかりました。

    class Points {

        String name;
        String address;
        int phone;
        int coord1;
        int coord2;

        // getters+setters
    };

    class PointsIdentifier {

        private String name;
        private String address;

        public PointsIdentifier(String name, String address) {
            this.name = name;
            this.address = address;

        }

        public boolean contains(String seq) {
            return name.contains(seq) || address.contains(seq);
        }

        @Override
        public boolean equals(Object obj) {
            Points other = (Points) obj;
            return name.equals(other.name) && address.equals(other.address);
        }

        @Override
        public int hashCode() {
            return name.hashCode() + address.hashCode();
        }
    };

    class PointsCollection {
        private Map<PointsIdentifier, Points> map;

        public PointsCollection() {
            map = new HashMap<PointsIdentifier, Points>();
        }

        public void add(Points p) {
            map.put(new PointsIdentifier(p.name, p.address), p);
        }

        public List<Points> findIdsContaining(String seq) {
            List<Points> resultList = new ArrayList<Points>();
            for (Entry<PointsIdentifier, Points> entry : map.entrySet()) {
                if (entry.getKey().contains(seq)) {
                    resultList.add(entry.getValue());
                }
            }
            // optionally cache result
            return resultList;
        }
    }

    public class Question_11881630 {

        public static void main(String[] args) {
            PointsCollection places = createCollection(10000);
            System.out.println("Collection created");
        String seq = "1";

        System.out.format("Searching for: \"%s\"\n", seq);
        List<Points> verifySearch = verifySearch(places, seq);
        //show(verifySearch);
    }

    private static void show(List<Points> verifySearch) {
        int i = 1;
        for (Points p : verifySearch) {
            System.out.println(i + ": " + p.name + ", " + p.address);
            i++;
        }
    }

    private static List<Points> verifySearch(PointsCollection places, String seq) {
        long start = System.currentTimeMillis();
        List<Points> searchResult = places.findIdsContaining(seq);
        System.out.println("Search results: " + searchResult.size());
        long end = System.currentTimeMillis();
        System.out.println("Operation time: " + formatTime(end - start));
        return searchResult;
    }

    private static String formatTime(long elapsed) {
        return elapsed + " miliseconds";
    }

    private static PointsCollection createCollection(int number) {
        PointsCollection coll = new PointsCollection();
        while (number > 0) {
            coll.add(createSamplePoint(number));
            number--;
        }
        return coll;
    }

    private static Points createSamplePoint(int number) {
        Points p = new Points();
        p.name = "VeryVeryLongName: " + number;
        p.address = "VeryVeryLongLongAddress: " + number;
            p.coord1 = 123;
            p.coord2 = 456;
            return p;
        }
    }
于 2012-08-09T11:41:49.847 に答える
1

トライはぴったりのようです。特定のプレフィックスを持つすべての文字列を検索するのは効率的なデータ構造です。

代わりに既存の Java コレクションの 1 つを使用する場合は、TreeSetとそのfloor()メソッドを使用して、必要なプレフィックスの前に要素を取得し、一致している間にセットの反復を開始できます。

接頭辞だけでなく、部分文字列による検索を探している場合は、代わりに接尾辞ツリーを使用することをお勧めします。
Javaの既存のコンテナを使用する（非効率的な）代替手段は、キーのすべての部分文字列を aSetまたは aに格納Mapすることですが、2倍のスペースが必要になります。

于 2012-08-09T10:48:05.353 に答える