Traduction d'algorithmes Common Lisp en C++

a marqué ce sujet comme résolu.
Auteur du sujet

Bonjour.

J’ai tenté de traduire plusieurs algorithmes d’un papier (page 29) écrits en Common Lisp en C++, mais étant donné mon faible niveau en Lisp, je fais appel à vous pour m’assurer de la validité de ma version C++.

Algorithme 1

Version Common Lisp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
defun ph-and-p (ln mask)
  (loop for i in ln
        for hv = (logand i mask) do
    (if (eql (aref *ht* hv) mask) ;; ht est un tableau global de taille suffisante pour l'algorithme
        (return nil)
      (setf (aref *ht* hv) mask))
    finally return t))

defun ph-and (ln) ;; LN is an integer list
  (if (null (cdr ln))
    1
  (let ((mask (logxor (apply #’logior ln) (apply #’logand ln)))) ;; MASK consists of all discriminant bits
    (fill *ht* nil :start 0 :end (1+ mask)) ;; resets *HT*
    (loop for b from (highest-bit mask) by 1 downto 0
      when (logbitp b mask) do ;; for each 1-bit in MASK
      (let ((new (logxor mask (ash 1 b)))) ;; NEW = MASK with switched bit
        (when (ph-and-p ln new) (setf mask new)))
      finally return (1+ mask)))))

Version C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
bool ph_and_p(std::vector<std::size_t> const& ln, std::size_t mask)
{
        std::vector<bool> seen(mask + 1, false); // Le ht de la version Lisp, j'ai choisi d'utiliser une variable locale
        for (auto i : ln)
        {
                std::size_t hv{i & mask};
                if (seen[hv])
                        return false;

                seen[hv] = true;
        }

        return true;
}

std::size_t ph_and(std::vector<std::size_t> const& ln)
{
    if (ln.size() == 1)
        return 1;

    std::size_t acc_or{ln[0]};
    std::size_t acc_and{ln[0]};

    for (auto it = std::begin(ln) + 1 ; it < std::end(ln) ; ++it)
    {
        acc_or |= *it;
        acc_and &= *it;
    }

    std::size_t mask{acc_or ^ acc_and};

    for (int b{__builtin_ffsl(mask) - 1} ; b >= 0 ; --b)
    {
        if ((mask & (1 << b)) != 0)
        {
            std::size_t new_mask{mask ^ (1 << b)};
            if (ph_and_p(ln, new_mask))
                mask = new_mask;
        }
    }

    return mask + 1;
}

Algorithme 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
defun compute-least-free-ids-and (n mask)
  (loop for i in *free* until (= n 0) ;; free est un tableau global
        for hv =  (logand i mask)
        unless (eql (aref *ht* hv) mask)
        collect (progn (setf (aref *ht* hv) mask)
                       (decf n)
                       i)))

defun pn-and (ln n)
  (let ((mask (1- (ph-and ln))))
    (loop for b from 0 by 1
          while (> (+ (length ln) n) (ash 1 (logcount mask))) ;; when there are not enough 1-bits
          unless (logbitp b mask) ;; rightmost 0-bit
          do (setf mask (logxor mask (ash 1 b)))) ;; switch
    (ph-and-p ln mask) ;; resets *HT*
    (values (compute-least-free-ids-and n mask) (1+ mask))))

Version C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
std::vector<std::size_t> free_values;

std::vector<std::size_t> compute_least_free_ids_and(std::size_t n, std::size_t mask)
{
    std::vector<std::size_t> ids{};
    std::vector<bool> seen(mask + 1, false);
    for (std::size_t i : free_values)
    {
        if (n == 0)
            break;

        std::size_t hv{i & mask};
        if (seen[hv])
            continue;

        seen[hv] = true;
        ids.push_back(i);
        --n;
    }

    return ids;
}

std::pair<std::vector<std::size_t>, std::size_t> pn_and(std::vector<std::size_t> const& ln, std::size_t n)
{
    std::size_t mask{ph_and(ln) - 1};
    for (size_t b{0} ; (ln.size() + n) > (1 << __builtin_popcount(mask)) ; ++b)
    {
        if ((mask & (1 << b)) == 0)
            mask ^= 1 << b;
    }

    return std::make_pair(compute_least_free_ids_and(n, mask), mask + 1);
}

Merci.

Mon Github | Pony : Un langage à acteurs sûr et performant

+1 -1

Algorithme 1 : dans la condition de ton if, ligne 7, j’aurais plutôt écrit seen[hv] == mask. Autrement les eux codes me semblent correspondre. Il y a tout de même un truc qui me choque dans cette fonction : tu remplis ton tableau seen avec des valeurs, mais c’est une variable locale que tu ne renvoies jamais. Comment le reste du programme pourrait s’en servir ?

Algorithme 2 : même chose, ligne 12, condition du if : seen[hv]==mask. Ligne 16 : seen[hv] = mask. Il manque aussi un appel à ph-and-p pour réinitialiser le tableau seen. Il me semble que ce tableau devrait être global (ou passé par référence à tous les algos), car tes différents algos l’utilisent clairement pour se passer de l’information entre eux.

Au passage, je n’ai pas le courage de lire le papier, pourrais-tu expliquer en deux mots à quoi servent ces algos, ce qu’ils sont supposés faire ? Ça aiderait à vérifier si tout est OK (si ça se trouve, le code Lisp de base n’est pas parfait).

Et, BTW, ça fait bizarre de voir l’URL de mon labo ici. Rolland travaille à quelques couloirs de mon bureau. Le monde est petit.

Canis Lupus pour vous servir

+0 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte