使用可变键从表中查找vals

Question

这里有张桌子:

key由3个后缀组成:region + s1 + s2

区域,如美国总是被指定,但其他区域可以不指定,因此*将用于"所有".

例如:for key ="US_A_U"value = 2,因为:

1. 试图找到完全匹配:在表键中找到("US_A_U") - 未找到
2. 1步不太严格查找:查找键("US_A_*") - 找到== 2

for key ="US_Q_Q"value = 3,因为:

1. 试图找到完全匹配:在表键中找到("US_Q_Q") - 未找到
2. 1步不太严格查找:查找键("US_Q_*") - 未找到
3. 找到密钥("US _*_ Q") - 找不到
4. 1步不太严格查找:查找键(" US_*_*") - 找到= 3

for key ="US_O_P"value = 3,因为:

1. 试图找到完全匹配:在表键中找到("US_O_P") - 未找到
2. 1步不太严格查找:查找键("US_O_*") - 未找到
3. 找到密钥("US _*_ P") - 未找到
4. 1步不太严格查找:查找键(" US_*_*") - 找到= 3

所以要使用HashMap方法,我需要调用4次map.get()来查找一个值,这个值太多了,因为这段代码会经常运行.

有没有更好或更快的解决方案？

package test;

import java.util.HashMap;

public class MainCLass {

    public static void main(String[] args) {
        // init map (assuming this code will be run only once)
        HashMap<String, String> map = new HashMap<>();
        map.put("US_A_B", "1");
        map.put("US_A_*", "2");
        map.put("US_*_*", "3");
        map.put("US_O_O", "4");
        map.put("US_*_W", "5");
        map.put("ASIA_*_*", "6");

        // now often called logic
        // incoming params, for this example hardcoded
        String reg = "US";
        String s1 = "O";
        String s2 = "P";
        String val = null;
        val = map.get(reg+"_"+s1+"_"+s2);
        if (val == null){
            val = map.get(reg+"_"+s1+"_*");
            if (val == null){
                val = map.get(reg+"_"+"*_"+s2);
                if (val == null){
                    val = map.get(reg+"_*_*");
                }
            }
        }
        System.out.println(val);
    }
}

upd:我需要补充的是总有3个传入参数(区域,s1,s2).这个参数中的每一个永远不会相等"*"而且永远不会是空的,所以完整的密钥总是像US_J_K(而不是US_*_K等)

所以通过这3个参数,我需要从init表中找到正确的值.

Answer 1

您可以尝试创建一层地图，例如

Map<String, Map<String, Map<String, String>>> map;

在此映射中，第一个键是region，第二个键是s1，第三个键是s2。这将允许轻松地独立搜索区域、s1 和 s2。

编辑：

搜索“US_O_P”的用法示例

public static void main(String[] args) {
    RegionMap map = new RegionMap();
    String region = "US";
    String s1 = "O";
    String s2 = "P";
    String val = map.search(region, s1, s2);
    System.out.println(val);
}

public class RegionMap {
    private Map<String, Map<String, Map<String, String>>> regionMap;

    public RegionMap() {
        init();
    }

    public String search(String region, String s1, String s2) {
        String val = searchS1(regionMap.get(region), s1, s2);
        if (val == null) {
            val = searchS1(regionMap.get("*"), s1, s2);
        }
        return val;
    }

    private String searchS1(Map<String, Map<String, String>> s1Map, String s1, String s2) {
        if (s1Map == null) {
            return null;
        }
        String val = searchS2(s1Map.get(s1), s2);
        if (val == null) {
            val = searchS2(s1Map.get("*"), s2);
        }
        return val;
    }

    private String searchS2(Map<String, String> s2Map, String s2) {
        if (s2Map == null) {
            return null;
        }
        String val = s2Map.get(s2);
        if (val == null) {
            val = s2Map.get("*");
        }
        return val;
    }

    private void init() {
        regionMap = new HashMap<>();
        addEntry("US", "A", "B", "1");
        addEntry("US", "A", "*", "2");
        addEntry("US", "*", "*", "3");
        addEntry("US", "O", "O", "4");
        addEntry("US", "*", "W", "5");
        addEntry("ASIA", "*", "*", "6");
    }

    private void addEntry(String region, String s1, String s2, String value) {
        Map<String, Map<String, String>> s1Map = regionMap.get(region);
        if (s1Map == null) {
            s1Map = new HashMap<>();
            regionMap.put(region, s1Map);
        }

        Map<String, String> s2Map = s1Map.get(s1);
        if (s2Map == null) {
            s2Map = new HashMap<>();
            s1Map.put(s1, s2Map);
        }

        s2Map.put(s2, value);
    }
}

编辑：基准结果

我多次运行了搜索“US_O_P”的测试，并发现 1,000,000,000 次搜索的结果如下

Original: 9.7334702479 seconds
Tiered: 2.471287074 seconds

以下是基准代码

public class RegionMapOrig {
    private Map<String, String> map;

    public RegionMapOrig() {
        init();
    }

    private void init() {
        map = new HashMap<>();
        map.put("US_A_B", "1");
        map.put("US_A_*", "2");
        map.put("US_*_*", "3");
        map.put("US_O_O", "4");
        map.put("US_*_W", "5");
        map.put("ASIA_*_*", "6");
    }

    public String search(String reg, String s1, String s2) {
        String val = null;
        val = map.get(reg + "_" + s1 + "_" + s2);
        if (val == null) {
            val = map.get(reg + "_" + s1 + "_*");
            if (val == null) {
                val = map.get(reg + "_" + "*_" + s2);
                if (val == null) {
                    val = map.get(reg + "_*_*");
                }
            }
        }
        return val;
    }
}

private static final int N = 1000000000;

public static void main(String[] args) {
    String region = "US";
    String s1 = "O";
    String s2 = "P";

    testOrig(region, s1, s2);
    test(region, s1, s2);
}

private static void testOrig(String region, String s1, String s2) {
    RegionMapOrig map = new RegionMapOrig();

    long start = System.nanoTime();

    for (int i = 0; i < N; ++i) {
        String val = map.search(region, s1, s2);
    }

    long end = System.nanoTime();
    System.out.println((end - start) / 10E9);
}

private static void test(String region, String s1, String s2) {
    RegionMap map = new RegionMap();

    long start = System.nanoTime();

    for (int i = 0; i < N; ++i) {
        String val = map.search(region, s1, s2);
    }

    long end = System.nanoTime();
    System.out.println((end - start) / 10E9);
}

多次运行此代码会产生相同的结果。然而，这个基准很简单，可能不是确定的。要真正测试您的结果，您需要使用代表典型值的真实数据集来分析性能。我相信您的性能问题可能在于您的字符串连接，而不是对地图的调用次数。我的性能可能更好的另一个原因是我的内部映射可能会被缓存，从而使多次检索更快。

编辑：基准更新

经过进一步调查，通过删除字符串连接，您的原始代码得到了改进，显示了以下结果：

Orginal (no concatentation): 1.2068575417 seconds
Tiered: 2.2982665873 seconds

代码更改为：

public String searchNoCat(String cache1, String cache2, String cache3,  String cache4) {
    String val = null;
    val = map.get(cache1);
    if (val == null) {
        val = map.get(cache2);
        if (val == null) {
            val = map.get(cache3);
            if (val == null) {
                val = map.get(cache4);
            }
        }
    }
    return val;
}

private static void testOrigNoCat(String region, String s1, String s2) {
    RegionMapOrig map = new RegionMapOrig();

    String cache1 = region + "_" + s1 + "_" + s2;
    String cache2 = region + "_" + s1 + "_*";
    String cache3 = region + "_" + "*_" + s2;
    String cache4 = region + "_*_*";

    long start = System.nanoTime();

    for (int i = 0; i < N; ++i) {
        String val = map.searchNoCat(cache1, cache2, cache3, cache4);
    }

    long end = System.nanoTime();
    System.out.println((end - start) / 10E9);
}

然而，问题仍然在于如何有效地缓存这些值或减少通用输入的串联数量。我不知道有什么有效的方法可以做到这一点。因此，我认为分层映射是避免串联问题的有效解决方案。