用变量键从表中找到val

2018-07-03 20:09:57

这里有张桌子：

密钥由3个后缀组成：region + s1 + s2

地区，像美国一样总是指定，但其他的不能指定，所以*将用于“全部”。

例如：for key =“US_A_U”value = 2，因为：

试图找到完全匹配：找到表键（“US_A_U”） - 找不到

1步少严格找到：找到密钥（“US_A_ *”） - 找到== 2

对于key =“US_Q_Q”值= 3，因为：

试图找到完全匹配：找到表键（“US_Q_Q”） - 找不到

1步少严格找到：找到密钥（“US_Q_ *”） - 找不到

找到密钥（“US _ * _ Q”） - 找不到

1步少严格查找：找到密钥（“ US_*_* ”） - 找到= 3

对于key =“US_O_P”值= 3，因为：

试图找到完全匹配：找到表中键（“US_O_P”） - 找不到

1步少严格找到：找到密钥（“US_O_ *”） - 找不到

找到密钥（“US _ * _ P”） - 未找到

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表中找到正确的值。

你可以尝试创建一系列的地图，如

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

在这张图中，第一个键是区域，第二个键是s1，第三个键是s2。这将允许独立地轻松搜索region，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);
}

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

编辑：基准更新

通过删除字符串concatentation进一步调查你的原代码改进显示这些结果：

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);
}

但是，问题仍然是如何有效地缓存这些值或减少通用输入的连接数量。我不知道有效的方法来做到这一点。因此，我认为分层映射是避免级联问题的有效解决方案。

看起来您需要一些树结构来帮助您在搜索值时使用通配符（“*”）替换来封装逻辑。

首先我写了一些单元测试来描述预期的行为

import static org.junit.Assert.*;

import org.junit.Before;
import org.junit.Test;

public class WildcardSearchSpec {
    private Node root;

    @Before
    public void before() {
        root = new WildcardSearch();
        root.add("US_A_B", "1");
        root.add("US_A_*", "2");
        root.add("US_*_*", "3");
        root.add("US_O_O", "4");
        root.add("US_*_W", "5");
        root.add("ASIA_*_*", "6");
    }

    @Test
    public void itShouldReturnFullWildcardCorrespondingValue() {
        String key = "US_Q_Q";

        String value = root.value(key);

        assertEquals("3", value);
    }

    @Test
    public void itShouldReturnNoWildcardCorrespondingValue() {
        String key = "US_A_B";

        String value = root.value(key);

        assertEquals("1", value);
    }

    @Test
    public void itShouldReturnS2WildcardCorrespondingValue() {
        String key = "US_A_U";

        String value = root.value(key);

        assertEquals("2", value);
    }

    @Test
    public void itShouldReturnS1WidlcardCorrespondingValue() {
        String key = "US_W_W";

        String value = root.value(key);

        assertEquals("5", value);
    }

    @Test(expected=NoValueException.class)
    public void itShouldThrowWhenNoCorrespondingValue() {
        String key = "EU_A_B";

        root.value(key);

        fail();
    }
}

可以从这些测试中提取的接口如下

public interface Node {
    void add(String key, String value);
    String value(String key);
}

它由WildcardSearch实现

import java.util.HashMap;
import java.util.Map;

public final class WildcardSearch implements Node {
    private final Map<String, CountrySearch> children = new HashMap<>();

    @Override
    public void add(String key, String value) {
        String country = key.split("_")[0];
        String rest = key.substring(country.length() + 1);

        children.putIfAbsent(country, new CountrySearch());
        children.get(country).add(rest, value);
    }

    @Override
    public String value(String key) {
        String country = key.split("_")[0];
        String rest = key.substring(country.length() + 1);

        if (!children.containsKey(country)) {
            return children.get(country).value(rest);
        } else {
            throw new NoValueException();
        }
    }
}

WildcardSearch使用CountrySearch在每个国家委派搜索。

import java.util.HashMap;
import java.util.Map;

final class CountrySearch implements Node {
    private final Map<String, SuffixeSearch> children = new HashMap<>();

    @Override
    public void add(String key, String value) {
        String[] splittedKey = key.split("_");
        String s1 = splittedKey[0];
        String s2 = splittedKey[1];
        children.putIfAbsent(s1, new SuffixeSearch());
        children.get(s1).add(s2, value);
    }

    @Override
    public String value(String key) {
        String[] splittedKey = key.split("_");
        String s1 = splittedKey[0];
        String s2 = splittedKey[1];

        if (children.containsKey(s1)) {
            return children.get(s1).value(s2);
        } else if (children.containsKey("*")) {
            return children.get("*").value(s2);
        } else {
            throw new NoValueException();
        }
    }
}

CountrySearch使用SuffixeSearch委派的后缀搜索。

import java.util.HashMap;
import java.util.Map;

final class SuffixeSearch implements Node {
    private final Map<String, String> children = new HashMap<>();

    public void add(String key, String value) {
        children.put(key, value);
    }

    @Override
    public String value(String key) {
        if (children.containsKey(key)) {
            return children.get(key);
        } else if (children.containsKey("*")) {
            return children.get("*");
        } else {
            throw new NoValueException();
        }
    }
}

注意： NoValueException是一个自定义的RuntimeException 。

关键是每个责任都明确分开。

SuffixeSearch只能返回相应键的值或与“*”对应的值。它不知道整体关键结构如何，价值观是否按国家分组等等。

CountrySearch只知道其级别，将其余SuffixeSearch委托给SuffixeSearch或忽略上述内容。

WildcardSearch只知道在国家/地区分裂并委派CountrySearch负责执行通配魔术。

最好的和更一般的解决方案是使用一个搜索树，你可以很容易地实现自己，也是一个很好的编程练习。还有很多教程和示例，以及如何实现它。

对于您的特殊用例，您可以使用级联地图，因为DragonAssassin已发布，它利用了Java已经提供的内容。

链接地址: http://www.djcxy.com/p/94265.html

上一篇: finding vals from table with variable keys

下一篇: Load NgModule entryComponents dynamically using service