实现一个地图，其中键是套不重叠的范围 [英] Implementing a Map where keys are sets of non-overlapping ranges

问题描述

我使用列表和循环面临着我当前实现的性能问题。我想做出一些自定义的地图但有可能适当地覆盖吸气与以下安装工作：

I am facing a performance issue with my current implementation using List and loops. I was thinking to make some custom Map but is it possible to override the getter properly to work with following setup:

地图包含自定义对象和重点可以是以下内容：

Map contains custom objects and key can be following:

case A key: "10"
calling get("10") would return matching object

case B key: "10;12;14"
calling get("10"),get("12"),get("14") would return same object

case C key: "10;20-30"
calling get("10"), get(value between 20 and 30) would return same object

时使用地图在这种情况下的最佳方式，可能是什么选择呢？

Is using a Map in this kind of scenario the best way, what could be the alternatives?

感谢。

推荐答案

更新：加全面实施

更新2：：如果你愿意，你可以使用<一个href=\"http://docs.guava-libraries.google$c$c.com/git/javadoc/com/google/common/collect/RangeMap.html\"相对=nofollow> RangeMap 内部 theMap 作为意见提出的。

UPDATE 2: If you want you can use RangeMap for internal theMap as suggested in the comments.

如果您键入的范围没有重叠，您可以创建一个自定义的容器，在 TreeMap的内部存储数据与自定义键，它实现可比：

If you key ranges don't overlap, you can create a custom container which internally stores data in TreeMap with a custom key which implements Comparable:

class MyStorage<T> {
    private static final class Range implements Comparable<Range> {
        private int first;
        private int last;

        public Range(int first_, int last_) {
            first = first_;
            last = last_;
        }

        // This heavily relies on that the ranges don't overlap
        @Override public int compareTo(Range other) {
            if (last < other.first)
                return -1;
            if (first > other.last)
                return 1;
            return 0;
        }
    }

    private Map<Range, T> theMap = new TreeMap<Range, T>();

    public void put(String key, T obj) {
        String[] ranges = key.split(";");
        for (String range : ranges) {
            //System.out.println("Adding " + range);
            String[] bounds = range.split("-");
            //System.out.println("Bounds " + bounds.length);
            int first = Integer.parseInt(bounds[0]);
            if (bounds.length == 1)
                theMap.put(new Range(first, first), obj);
            else 
                theMap.put(new Range(first, Integer.parseInt(bounds[1])), obj);
        }
    }

    public T get(String key) {
        return get(Integer.parseInt(key));
    }

    public T get(int key) {
        return theMap.get(new Range(key, key));
    }
}

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        MyStorage<Integer> storage = new MyStorage<Integer>();
        storage.put("10;20-30", 123);
        storage.put("15;31-50", 456);

        System.out.println(storage.get("42"));
    }
}

这篇关于实现一个地图，其中键是套不重叠的范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！