Как создать карту диапазона в Java, когда ключи являются строками - PullRequest
Новая
       43

Как создать карту диапазона в Java, когда ключи являются строками

0 голосов
/ 31 мая 2018

Я хочу создать карту большого диапазона, в которой ключи, соответствующие их номерам, будут сопоставлены с сегментами, например: 

            NavigableMap<String, String> map = new TreeMap<>();

            map.put("var2#" + 0L,   "out0");      // "var2#0..100        => out0
            map.put("var2#" + 100L, "out1");    // "var2#100..200"     => out1
            map.put("var2#" + 200L, "out2");    // "var2#200..300"     => out2
            map.put("var2#" + 300L, "out3");    // "var2#300..+"       => out3

Это означает, что если новый ключ поступит со значением res, то оно должно быть "var2#150" ==> "out1"

То, что я пытался сделать, это использовать отсортированную карту, все работает с диапазоном чисел внутри карты

что-то вроде: 

String out1 = map.floorEntry("var2#" + 150L).getValue(); //out1 , works!

, но еслиотправьте var2 # 2000, вместо этого, чтобы получить res "out3", я получил "out2" и так далее ... 

String res = map.floorEntry("var2#" + 2000L).getValue(); 
Syso(res)  ==> out2 , BUT I expected result => "out3"
// because it is bigger that the range.

PS: 

It is very large map with prefix of some "string" and comes after typed
 long number . Eg. "var1#100, var1#200 , ...bla1#1000 , bla5#2000....

Еще одна проблема - когда яимеют одинаковое длинное значение на разных ключах, которые я собираюсь сделать первым соответствием для строки, а затем для числа ... 

    map.put("var1#" + 200L, "out0");
    map.put("var2#" + 200L, "out1");
    map.put("var3#" + 200L, "out2");
    map.put("var4#" + 200L, "out3");

    String out1 = map.floorEntry("var2#" + 150L).getValue();
    System.out.println("====> " + out1); //expected  out1 , because only match of "var2
    String out3 = map.floorEntry("var2#" + 250L).getValue(); //expected  out1 , because only match of "var2
    System.out.println("====> " + out3);" ....

Есть предложения, пожалуйста, возможно, какой-нибудь алгоритм?

Ответы [ 4 ]

0 голосов
/ 31 мая 2018

Один из способов сравнения префикса по строке с последующим числовым сравнением суффикса может быть следующим: 

public static int compareParts(String a, String b) {
    String[] aa = a.split("#", 2), ba = b.split("#", 2);
    int c = aa[0].compareTo(ba[0]);
    return c != 0? c: Integer.compare(Integer.parseInt(aa[1]), Integer.parseInt(ba[1]));
}

Но поскольку методы сравнения могут вызываться очень часто, даже один поиск может включать несколько сравненийСтоит потратить некоторое время на улучшение производительности, даже если код будет выглядеть более сложным: 

public static int compareParts(String a, String b) {
    final int aLen = a.length(), bLen = b.length(), l = Math.min(aLen, bLen);
    int ix = 0;
    stringPart: {
        for(; ix < l; ix++) {
            char aCh = a.charAt(ix), bCh = b.charAt(ix);
            int cmp = Character.compare(aCh, bCh);
            if(cmp != 0)
                return aCh == '#'? -1: bCh == '#'? +1: cmp;
            if(aCh == '#') break stringPart;
        }
        return 0;
    }
    // number part
    int aIx = ix+1, bIx = aIx;
    while(aIx < aLen && a.charAt(aIx)=='0') aIx++;
    while(bIx < bLen && b.charAt(bIx)=='0') bIx++;
    int cmp = Integer.compare(aLen-aIx, bLen-bIx);
    for(; cmp == 0 && aIx < aLen; aIx++, bIx++) {
        cmp = Character.compare(a.charAt(aIx), b.charAt(bIx));
    }
    return cmp;
}

Это только один проход по строке.Во-первых, он перебирает первые символы строки, как это делал бы String.compareTo, останавливаясь на первом несовпадающем символе или символе '#'.Если только одна строка встречается с '#', другая имеет более длинный префикс, и мы должны учитывать это для результата.

Только если обе строки имеют одинаковый префикс, числовая часть после '#' обрабатывается,Вместо выполнения полного целочисленного анализа мы пропускаем все ведущие нули, если они есть.Затем, если длина оставшейся значимой части отличается, это уже указывает, какое число больше.Только если значимые части имеют одинаковую длину, нам нужно их итерировать.Но мы можем сравнивать цифры буквально без необходимости интерпретировать их как числа в этом случае, так как порядок итераций уже от самой значащей цифры к младшей значащей цифре.

Любой метод может быть использован как 

NavigableMap<String, String> map = new TreeMap<>(MyClass::compareParts);

map.put("var2#" + 0L,   "out0");
map.put("var2#" + 100L, "out1");
map.put("var2#" + 200L, "out2");
map.put("var2#" + 300L, "out3");

String out1 = map.floorEntry("var2#" + 150L).getValue();
System.out.println("out1 = "+out1);
String out3 = map.floorEntry("var2#" + 2000L).getValue();
System.out.println("res = "+out3);
0 голосов
/ 31 мая 2018

Вы можете извлечь 2-ю часть ключа и использовать ее в качестве компаратора для навигационной карты: 

Comparator.comparingLong(key -> Long.parseLong(key.split("#")[1]))

Итак: 

NavigableMap<String, String> map =
    new TreeMap<>(Comparator.comparingLong(key -> Long.parseLong(key.split("#")[1])));

map.put("var2#" + 0L,   "out0");    // "var2#0..100        => out0
map.put("var2#" + 100L, "out1");    // "var2#100..200"     => out1
map.put("var2#" + 200L, "out2");    // "var2#200..300"     => out2
map.put("var2#" + 300L, "out3");    // "var2#300..+"       => out3

assertThat(map.floorEntry("var2#" + 150L).getValue()).isEqualTo("out1");
assertThat(map.floorEntry("var2#" + 2000L).getValue()).isEqualTo("out3");
0 голосов
/ 31 мая 2018

Я бы разделил ключ, чтобы получить Map диапазона для каждой переменной: 

Map<String, Ranges> map;

Где мы реализуем Ranges, поскольку нам нужно отобразить значение и результат, как предложено Хари Менон .

class Ranges {

    NavigableMap<Long, String> map = new TreeMap<>();

    public String setFloor(long l, String s){
        return map.put(l, s);
    }

    public String getFloor(long l){
        return map.floorEntry(l).getValue();
    }
}

Это будет просто заполнить: 

Map<String, Ranges> map = new HashMap<>();

Ranges r = new Ranges();
r.setFloor(0L, "out1");
r.setFloor(100L, "out2");   
map.put("var1", r);

r = new Ranges();
r.setFloor(0L, "out3");
r.setFloor(100L, "out4");
map.put("var2", r);

System.out.println(map.get("var1").getFloor(50L));
System.out.println(map.get("var2").getFloor(150L));

out1
out4

Мы можем использовать NavigableMap вместоиз HashMap, но я не вижу в этом смысла.

Обратите внимание, что это небезопасно для NPE, оно не было защищено, чтобы сделать решение коротким и читабельным.

0 голосов
/ 31 мая 2018

Проблема в том, что TreeMap использует строку для сравнения.Таким образом, он сортируется в алфавитном порядке, и var2#2000 находится между var2#200 и var2#300.Вам следует либо указать собственный компаратор , либо использовать Long или Integer в качестве ключа для TreeMap.Итак, это должно работать: 

NavigableMap<Long, String> map = new TreeMap<>();
map.put(0L,   "out0");      // "var2#0..100        => out0
map.put(100L, "out1");    // "var2#100..200"     => out1
map.put(200L, "out2");    // "var2#200..300"     => out2
map.put(300L, "out3");    // "var2#300..+"       => out3
...