Good ha sh функция для разделения идентификатора с помощью мода - PullRequest
Новая
       9

Good ha sh функция для разделения идентификатора с помощью мода

0 голосов
/ 06 марта 2020

У меня есть пакет идентификаторов, я хочу разделить их с хорошей функцией распространения лайнера.
Идентификаторы не содержат метки времени и действительно плохо распространяются. Я ограничен несколькими тупыми операторами xpath .

Не могли бы вы предложить лучшую функцию для распределения идентификаторов между 10 сегментами? 

public static void main(String[] args) {
    int[] buckets = new int[10];
    for (int i = 0; i < 10; i++)
        buckets[i] = 0;

    for (int i = 0; i < 1000; i++) {
        String id = format("130770%s0020", i);
        long l = parseLong(id);
        int partition = (int) f(l);
        buckets[partition] = buckets[partition] + 1;
    }

    for (int i = 0; i < 10; i++)
        out.println(buckets[i]);
}

В настоящее время мой лучший результат 

private static long f(long l) {
    return l % 31 % 10;
}

, что дает

130 96 97 96 97 97 96 98 97 96

Можете ли вы предложить лучшую реализацию?

Вот как код, который я редактирую, выглядит как 

<rule id="trade_to_backet_4">
    <forall var="trade_identifier" in="/eMxML/msml/trade/systemReference[1]/@reference">
        <equal op1="translate($trade_identifier, translate($trade_identifier,'0123456789',''), '') mod 813 mod 10" op2="4"/>
    </forall>
</rule>

Ответы [ 4 ]

2 голосов
/ 06 марта 2020

Если ваша цель состоит в том, чтобы вещи равномерно распределялись по корзинам, это похоже на работу: 

return ((l / 10000) % 1000) % 10;

(Это просто извлечение i обратно из числа)

Ideone demo .

Вывод: 

100 100 100 100 100 100 100 100 100 100

Альтернатива, которая, похоже, дает тот же результат: 

// NB: abs(int) isn't always non-negative. Should really handle Integer.MIN_VALUE.
return Math.abs(Long.toString(l).hashCode()) % 10;

Ideone демо

Выход: 

100 100 100 100 100 100 100 100 100 100
1 голос
/ 06 марта 2020

Вы ищете решение, которое бы хорошо работало с вашей конкретной партией идентификаторов, или с любой партией идентификаторов, или с партиями, которые имеют некоторые особые характеристики (например, все в форме 130770% s0020)?

Я думаю, что решения, использующие только целочисленную арифметику c, всегда будут плохо работать в каком-то наихудшем сценарии ios, например, когда все идентификаторы кратны 31. Вам действительно нужно выполнить некоторую битовую перестановку, которая не может быть эффективно реализовано в XPath 1.0.

Сказав это, я думаю, что я пытаюсь сделать следующее: выбрать 3 простых числа P, Q и R и вернуть (N mod P + N mod Q + N mod R) mod 10.

Стоит также помнить, что совершенный алгоритм не доставит одинаковое количество предметов в каждом ведре; скорее результат будет в лучшем случае отражать случайное распределение, то есть оно будет биномиальным. И вам нужно провести довольно умное тестирование на большом наборе входных данных, чтобы увидеть, достигли ли вы этого.

На этом этапе я склонен сделать шаг назад и спросить: что вы на самом деле делаете что требует этой функции ha sh? Есть ли другой способ решения проблемы, который не требует этой функции ha sh? Можете ли вы рассказать нам реальную проблему, которую вы пытаетесь решить?

1 голос
/ 06 марта 2020

Я бы порекомендовал выбрать то же решение, которое применялось к классу HashMap. 

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Для вашего кода это означало бы: 

return (l ^ (l >>> 16)) % 10;

С вашими тестовыми данными , который производит распространение: 

109 102 103 94 91 95 93 100 104 109

От комментарий :

У меня нет смены

Выражение l >>> 16 также может быть записано l / 65536, но деление намного медленнее, чем сдвиг битов, поэтому обычно вы используете l >>> 16.

ОБНОВЛЕНИЕ Из другого комментария :

У меня нет оператора XOR

Используйте + вместо ^. Хотя это и не так хорошо, но здесь это кажется достаточно хорошим: 

return (l + (l / 65536)) % 10;

Результирующий спред: 

101 92 92 99 105 104 105 99 97 106
0 голосов
/ 06 марта 2020

813 - действительно выдающееся число

101 101 101 100 100 99 99 99 100 100
101 101 101 100 100 100 100 99 99 99
101 100 100 99 100 100 100 100 100 100 100
101 101 101 100 100 100 99 99 99 100
101 101 101 100 100 100 100 99 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
1 01 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99
101 101 101 100 100 100 100 99 99 99 

private static final int GROUP_SIZE = 1000;
private static final int BUCKET_SIZE = 10;
private static final double MAX_DEVIATION = BUCKET_SIZE * 1.0;
private static final int NUMBER_TO_TEST = 813;

public static void main(String[] args) {
    List<Long> list = LongStream.range(1, 1000).boxed().parallel()
            .filter(l -> filter("005001307700020%s", l))
            .filter(l -> filter("0050013077%s00020", l))
            .filter(l -> filter("00500%s1307700020", l))
            .filter(l -> filter("%s005001307700020", l))
            .filter(l -> filter("111111111111111%s", l))
            .filter(l -> filter("1111111111%s11111", l))
            .filter(l -> filter("11111%s1111111111", l))
            .filter(l -> filter("%s111111111111111", l))
            .filter(l -> filter("222222222222222%s", l))
            .filter(l -> filter("2222222222%s22222", l))
            .filter(l -> filter("22222%s2222222222", l))
            .filter(l -> filter("%s222222222222222", l))
            .filter(l -> filter("333333333333333%s", l))
            .filter(l -> filter("3333333333%s33333", l))
            .filter(l -> filter("33333%s3333333333", l))
            .filter(l -> filter("%s333333333333333", l))
            .filter(l -> filter("444444444444444%s", l))
            .filter(l -> filter("4444444444%s44444", l))
            .filter(l -> filter("44444%s4444444444", l))
            .filter(l -> filter("%s444444444444444", l))
            .filter(l -> filter("555555555555555%s", l))
            .filter(l -> filter("5555555555%s55555", l))
            .filter(l -> filter("55555%s5555555555", l))
            .filter(l -> filter("%s555555555555555", l))
            .filter(l -> filter("666666666666666%s", l))
            .filter(l -> filter("6666666666%s66666", l))
            .filter(l -> filter("66666%s6666666666", l))
            .filter(l -> filter("%s666666666666666", l))
            .filter(l -> filter("777777777777777%s", l))
            .filter(l -> filter("7777777777%s77777", l))
            .filter(l -> filter("77777%s7777777777", l))
            .filter(l -> filter("%s777777777777777", l))
            .filter(l -> filter("888888888888888%s", l))
            .filter(l -> filter("8888888888%s88888", l))
            .filter(l -> filter("88888%s8888888888", l))
            .filter(l -> filter("%s888888888888888", l))
            .filter(l -> filter("999999999999999%s", l))
            .filter(l -> filter("9999999999%s99999", l))
            .filter(l -> filter("99999%s9999999999", l))
            .filter(l -> filter("%s999999999999999", l))
            .collect(toList());
    System.err.println(list);
}

public static boolean filter(String format, long number) {
    int[] buckets = new int[BUCKET_SIZE];
    for (int i = 0; i < BUCKET_SIZE; i++)
        buckets[i] = 0;

    for (int i = 0; i < GROUP_SIZE; i++) {
        String id = format(format, i);
        long l = parseLong(id);
        int partition = (int) (l % number % BUCKET_SIZE);
        buckets[partition] = buckets[partition] + 1;
    }

    int sum = 0;
    for (int i = 0; i < BUCKET_SIZE; i++)
        sum += buckets[i];

    int deviation = 0;
    for (int i = 0; i < BUCKET_SIZE; i++)
        deviation += abs(buckets[i] - sum / BUCKET_SIZE);

    if (number == NUMBER_TO_TEST) {
        for (int i = 0; i < BUCKET_SIZE; i++)
            System.out.println(buckets[i]);
        System.out.println("----------------------");
    }
    return deviation < MAX_DEVIATION;
}
...