Calculez le nombre maximal d'exécutions possibles pour une chaîne aussi grande que possible

24

[Cette question est un suivi pour calculer les exécutions d'une chaîne ]

Une période pd'une chaîne west un entier positif ptel que w[i]=w[i+p] chaque fois que les deux côtés de cette équation sont définis. Soit per(w)la taille de la plus petite période de w. On dit qu'une chaîne west périodique ssi per(w) <= |w|/2.

Donc, officieusement, une chaîne périodique n'est qu'une chaîne composée d'une autre chaîne répétée au moins une fois. La seule complication est qu'à la fin de la chaîne, nous n'avons pas besoin d'une copie complète de la chaîne répétée tant qu'elle est répétée dans son intégralité au moins une fois.

Par exemple, considérez la chaîne x = abcab. per(abcab) = 3comme x[1] = x[1+3] = a, x[2]=x[2+3] = bet il n'y a pas de période plus courte. La chaîne abcabn'est donc pas périodique. Cependant, la chaîne ababaest périodique comme per(ababa) = 2.

Comme plus d' exemples, abcabca, ababababaet abcabcabcsont également périodiques.

Pour ceux qui aiment les regex, celui-ci détecte si une chaîne est périodique ou non:

\b(\w*)(\w+\1)\2+\b

La tâche consiste à trouver toutes les sous- chaînes périodiques maximales dans une chaîne plus longue. Celles-ci sont parfois appelées « runs» dans la littérature.

Une sous w- chaîne est une sous-chaîne périodique maximale (run) si elle est périodique et ni w[i-1] = w[i-1+p]ni ni w[j+1] = w[j+1-p]. De manière informelle, le «run» ne peut pas être contenu dans un «run» plus grand avec la même période.

Étant donné que deux exécutions peuvent représenter la même chaîne de caractères se trouvant à différents endroits de la chaîne globale, nous représenterons les exécutions par intervalles. Voici la définition ci-dessus répétée en termes d'intervalles.

Une exécution (ou sous-chaîne périodique maximale) dans une chaîne Test un intervalle [i...j]avec j>=i, tel que

  • T[i...j] est un mot périodique avec la période p = per(T[i...j])
  • C'est maximal. Formellement, ni T[i-1] = T[i-1+p]ni T[j+1] = T[j+1-p]. De manière informelle, l'exécution ne peut pas être contenue dans une exécution plus grande avec la même période.

Indique RUNS(T)l'ensemble des exécutions en chaîne T.

Exemples de runs

  • Les quatre sous - chaînes périodiques maximale (runs) en chaîne T = atattattsont T[4,5] = tt, T[7,8] = tt, T[1,4] = atat, T[2,8] = tattatt.

  • La chaîne T = aabaabaaaacaacaccontient les 7 sous - chaînes périodiques maximales suivantes (runs): T[1,2] = aa, T[4,5] = aa, T[7,10] = aaaa, T[12,13] = aa, T[13,16] = acac, T[1,8] = aabaabaa, T[9,15] = aacaaca.

  • La chaîne T = atatbatatbcontient les trois exécutions suivantes. Ils sont: T[1, 4] = atat, T[6, 9] = atatet T[1, 10] = atatbatatb.

Ici, j'utilise l'indexation 1.

La tâche

Écrivez le code de sorte que pour chaque entier n commençant à 2, vous produisiez le plus grand nombre d'exécutions contenues dans n'importe quelle chaîne binaire de longueur n.

But

Votre score est le plus élevé que nvous atteignez en 120 secondes de sorte que pour tous k <= n, personne d'autre n'a posté une réponse correcte plus élevée que vous. De toute évidence, si vous avez toutes les réponses optimales, vous obtiendrez le score le plus élevé que nvous publiez. Cependant, même si votre réponse n'est pas optimale, vous pouvez toujours obtenir le score si personne d'autre ne peut le battre.

Langues et bibliothèques

Vous pouvez utiliser toutes les langues et bibliothèques disponibles que vous aimez. Dans la mesure du possible, il serait bon de pouvoir exécuter votre code, veuillez donc inclure une explication complète sur la façon d'exécuter / compiler votre code sous Linux si possible.

Exemple optima

Dans ce qui suit: n, optimum number of runs, example string.

2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011

Que doit exactement sortir mon code?

Pour chacun, nvotre code doit sortir une seule chaîne et le nombre d'exécutions qu'il contient.

Ma machine Les horaires seront exécutés sur ma machine. Il s'agit d'une installation ubuntu standard sur un processeur AMD FX-8350 à huit cœurs. Cela signifie également que je dois pouvoir exécuter votre code.

Réponses principales

  • 49 par Anders Kaseorg en C . Simple thread et exécuté avec L = 12 (2 Go de RAM).
  • 27 par cdlane en C .
Communauté
la source
1
Si vous souhaitez que nous considérions uniquement les {0,1}chaînes de caractères, veuillez l'indiquer explicitement. Sinon, l'alphabet pourrait être infini, et je ne vois pas pourquoi vos tests devraient être optimaux, car il semble que vous n'ayez recherché que les {0,1}chaînes.
flawr
3
@flawr, j'ai recherché des chaînes sur un alphabet ternaire njusqu'à 12et il n'a jamais battu l'alphabet binaire. Heuristiquement, je m'attendrais à ce qu'une chaîne binaire soit optimale, car l'ajout de caractères augmente la longueur minimale d'une exécution.
Peter Taylor
1
Dans les résultats optimaux ci-dessus, vous avez "12 7 001001010010" mais mon code affiche "12 8 110110011011" où les périodes de la période 1 sont (11, 11, 00, 11, 11), les périodes de la période 3 sont (110110, 011011) et il y a une période de 4 run (01100110) - où vais-je mal dans mon comptage de run?
cdlane
1
@cdlane 0000 a une exécution. Considérez la période de 000 ... c'est toujours 1 quel que soit le nombre de zéros.

Réponses:

9

C

Cela effectue une recherche récursive de solutions optimales, fortement élaguées en utilisant une limite supérieure sur le nombre d'exécutions qui pourraient être terminées par le reste inconnu de la chaîne. Le calcul de la borne supérieure utilise une gigantesque table de consultation dont la taille est contrôlée par la constante L( L=11: 0,5 Gio L=12,: 2 Gio L=13,: 8 Gio).

Sur mon ordinateur portable, cela passe par n = 50 en 100 secondes; la ligne suivante arrive à 142 secondes.

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 << 2*L][2], small[N + 1][2 << 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state >= 2 << 2*L) {
        state &= ~(2 << 2*L);
        state |= 1 << 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p > 0; p--) {
            if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                m |= 1ULL << start[p];
                r++;
            }
        }
        if (r > best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p > i; p--)
                if (p > L)
                    bound += (n - p + 1)/(p + 1);
            for (; p > 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                        m |= 1ULL << start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p > L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p > L)
                        bound += (n - (start[p] + p - 1 > i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound > best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n <= N; n++) {
        if (n <= 2*L) {
            for (unsigned state = 1U << n; state < 2U << n; state++) {
                for (int b = 0; b < 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p > 0; p--) {
                        if ((b ^ state >> (p - 1)) & 1) {
                            unsigned k = state ^ state >> p;
                            k &= -k;
                            k <<= p;
                            if (!(k & ~(~0U << n)))
                                k = 1U << n;
                            if (!((m | ~(~0U << 2*p)) & k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L < n - 1 ? 2*L : n - 1; l >= 0; l--) {
            for (unsigned state = 1U << l; state < 2U << l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 > r1 ? r0 : r1;
            }
        }

        if (n >= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i < n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}

Sortie:

$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100

Voici toutes les séquences optimales pour n ≤ 64 (pas seulement lexicographiquement en premier), générées par une version modifiée de ce programme et de nombreuses heures de calcul.

Une séquence remarquable presque optimale

Les préfixes de la séquence fractale infinie

1010010110100101001011010010110100101001011010010100101…

qui est invariant sous la transformation 101 ↦ 10100, 00 ↦ 101:

  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …

semblent avoir un nombre d'exécutions presque optimal - toujours à moins de 2 de l'optimal pour n ≤ 64. Le nombre d'exécutions dans les n premiers caractères divisé par n approches (13 - 5√5) / 2 ≈ 0,90983. Mais il s'avère que ce n'est pas le rapport optimal - voir les commentaires.

Anders Kaseorg
la source
Merci la réponse et vos corrections. Selon vous, quelles sont les perspectives d'une solution sans force brute?
1
@Lembik je ne sais pas. Je pense que ma solution actuelle est un peu plus rapide que o (2 ^ N) avec suffisamment de mémoire, mais elle est toujours exponentielle. Je n'ai pas trouvé de formule directe qui ignore complètement le processus de recherche, mais une pourrait exister. Je suppose que la séquence de Thue – Morse est asymptotiquement optimale avec N runs5 / 6 - O (log N), mais elle semble rester une poignée de pistes derrière l'optimum réel.
Anders Kaseorg
Fait intéressant, 42/50> 5/6.
1
@Lembik On devrait toujours s'attendre à ce que les prédictions asymptotiques soient parfois battues par petites quantités. Mais en fait, je me trompais complètement - j'ai trouvé une bien meilleure séquence qui semble approcher N runs (13 - 5√5) / 2 ≈ N⋅0.90983.
Anders Kaseorg
Très impressionnant. Je pense cependant que la conjecture 0.90983 n'est pas correcte. Consultez bpaste.net/show/287821dc7214 . Il a une longueur de 1558 et 1445 pistes.
2

Comme ce n'est pas une course s'il n'y a qu'un seul cheval, je soumets ma solution bien qu'elle ne soit qu'une fraction de la vitesse d'Anders Kaseorg et un tiers seulement comme cryptique. Compiler avec:

gcc -O2 run-count.c -o run-count

Le cœur de mon algorithme est un simple décalage et schéma XOR:

entrez la description de l'image ici

Une exécution de zéros dans le résultat XOR qui est supérieure ou égale à la période / décalage en cours indique une exécution dans la chaîne d'origine pour cette période. De là, vous pouvez dire combien de temps a duré la course et où elle commence et se termine. Le reste du code est une surcharge, la configuration de la situation et le décodage des résultats.

J'espère que cela fera au moins 28 après deux minutes sur la machine de Lembik. (J'ai écrit une version pthread, mais j'ai seulement réussi à la faire fonctionner encore plus lentement.)

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

enum { START = 0, WIDTH } ;

// Compare and shuffle just one thing while storing two
typedef union {
    uint16_t token;
    uint8_t data[sizeof(uint16_t)];
} overlay_t;

#define SENTINAL (0)  // marks the end of an array of overlay_t

#define NUMBER_OF_BITS (8 * sizeof(uint64_t))

void period_runs(uint64_t xor_bits, uint8_t nbits, uint8_t period, overlay_t *results) {

    overlay_t *results_ptr = results;
    uint8_t count = 0;

    for (uint8_t position = 0; position < nbits; position++) {

        if (xor_bits & 1ULL) {

            if ((nbits - position) < period) {
                break;  // no room left to succeed further
            }

            if (count >= period) {  // we found a run

                results_ptr->data[START] = position - (count - 1);
                results_ptr->data[WIDTH] = period + count;
                results_ptr++;
            }

            count = 0;
        } else {

            count++;
        }

        xor_bits >>= 1;
    }

    if (count >= period) {  // process the final run, if any

        results_ptr->data[START] = 0;
        results_ptr->data[WIDTH] = period + count;
        results_ptr++;
    }

    results_ptr->token = SENTINAL;
}

void number_runs(uint64_t number, uint8_t bit_length, overlay_t *results) {

    overlay_t sub_results[bit_length];
    uint8_t limit = bit_length / 2 + 1;
    uint64_t mask = (1ULL << (bit_length - 1)) - 1;

    overlay_t *results_ptr = results;
    results_ptr->token = SENTINAL;

    for (uint8_t period = 1; period < limit; period++) {

        uint64_t xor_bits = mask & (number ^ (number >> period));  // heart of the code
        period_runs(xor_bits, bit_length - period, period, sub_results);

        for (size_t i = 0; sub_results[i].token != SENTINAL; i++) {

            bool stop = false;  // combine previous and current results

            for (size_t j = 0; !stop && results[j].token != SENTINAL; j++) {

                // lower period result disqualifies higher period result over the same span 
                stop = (sub_results[i].token == results[j].token);
            }

            if (!stop) {

                (results_ptr++)->token = sub_results[i].token;
                results_ptr->token = SENTINAL;
            }
        }

        mask >>= 1;
    }
}

int main() {

    overlay_t results[NUMBER_OF_BITS];

    for (uint8_t bit_length = 2; bit_length < 25; bit_length++) {

        int best_results = -1;
        uint64_t best_number = 0;

        for (uint64_t number = 1ULL << (bit_length - 1); number < (1ULL << bit_length); number++) {

            // from the discussion comments, I should be able to solve this
            // with just bit strings that begin "11...", so toss the rest
            if ((number & (1ULL << (bit_length - 2))) == 0ULL) {

                continue;
            }

            uint64_t reversed = 0;

            for (uint8_t i = 0; i < bit_length; i++) {

                if (number & (1ULL << i)) {

                    reversed |= (1ULL << ((bit_length - 1) - i));
                }
            }

            if (reversed > number) {

                continue;  // ~ 1/4 of bit_strings are simply reversals, toss 'em
            }

            number_runs(number, bit_length, results);
            overlay_t *results_ptr = results;
            int count = 0;

            while ((results_ptr++)->token != SENTINAL) {

                count++;
            }

            if (count > best_results) {

                best_results = count;
                best_number = number;
            }
        }

        char *best_string = malloc(bit_length + 1);
        uint64_t number = best_number;
        char *string_ptr = best_string;

        for (int i = bit_length - 1; i >= 0; i--) {

            *(string_ptr++) = (number & (1ULL << i)) ? '1' : '0';
        }

        *string_ptr = '\0';

        printf("%u %d %s\n", bit_length, best_results, best_string);

        free(best_string);
    }

    return 0;
}

Sortie:

> gcc -O2 run-count.c -o run-count
> ./run-count
2 1 11
3 1 110
4 2 1100
5 2 11000
6 3 110011
7 4 1100100
8 5 11001100
9 5 110010011
10 6 1100110011
11 7 11001100100
12 8 110110011011
13 8 1100100010011
14 10 11001001100100
15 10 110010011001000
16 11 1100100110010011
17 12 11001100100110011
18 13 110011001001100100
19 14 1101001011010010100
20 15 11010110100101101011
21 15 110010011001001100100
22 16 1100101001011010010100
23 17 11010010110100101001011
24 18 110100101001011010010100
25 19 1100100110010001001100100
26 20 11010010100101101001010010
27 21 110010011001000100110010011
28 22 1101001010010110100101001011
cdlane
la source
Bienvenue deuxième cheval! Petite question, pourquoi vous et l'autre réponse proposez -O2 au lieu de -O3?
@Lembik, avec l'optimisation -O2, je pouvais mesurer une différence de temps en exécutant le code mais je ne pouvais pas en mesurer plus avec -O3. Puisque nous sommes censés échanger en toute sécurité pour la vitesse, j'ai pensé que le niveau le plus élevé qui avait réellement fait la différence était le meilleur. Si vous croyez que mon code se classera plus haut avec -O3, allez-y!
cdlane
-O3n'est pas censé être «dangereux». Il permet l'auto-vectorisation, mais il n'y a probablement rien à vectoriser ici. Il peut parfois ralentir le code, par exemple s'il utilise un cmov sans branche pour quelque chose où une branche aurait très bien prédit. Mais en général, cela devrait aider. Il vaut généralement aussi la peine d'essayer clang, pour voir lequel de gcc ou clang fait un meilleur code pour une boucle spécifique. En outre, il est presque toujours utile d'utiliser -march=native, ou du moins -mtune=nativesi vous voulez toujours un binaire qui s'exécute n'importe où.
Peter Cordes