C'è un modo più veloce di convertire un numero in un nome?

Question

Il seguente codice definisce una sequenza di nomi associati ai numeri. È progettato per prendere un numero e recuperare un nome specifico. La classe opera assicurandosi che il nome esista nella sua cache e quindi restituisce il nome indicizzandolo nella sua cache. La domanda in questo: come si può calcolare il nome in base al numero senza memorizzare una cache?

Il nome può essere pensato come un numero di base 63, ad eccezione della prima cifra che è sempre della base 53.

class NumberToName: 

    def __generate_name(): 
     def generate_tail(length): 
      if length > 0: 
       for char in NumberToName.CHARS: 
        for extension in generate_tail(length - 1): 
         yield char + extension 
      else: 
       yield '' 
     for length in itertools.count(): 
      for char in NumberToName.FIRST: 
       for extension in generate_tail(length): 
        yield char + extension 

    FIRST = ''.join(sorted(string.ascii_letters + '_')) 
    CHARS = ''.join(sorted(string.digits + FIRST)) 
    CACHE = [] 
    NAMES = __generate_name() 

    @classmethod 
    def convert(cls, number): 
     for _ in range(number - len(cls.CACHE) + 1): 
      cls.CACHE.append(next(cls.NAMES)) 
     return cls.CACHE[number] 

    def __init__(self, *args, **kwargs): 
     raise NotImplementedError() 

le seguenti sessioni interattive mostrano alcuni dei valori che dovrebbero essere restituito in ordine.

>>> NumberToName.convert(0) 
'A' 
>>> NumberToName.convert(26) 
'_' 
>>> NumberToName.convert(52) 
'z' 
>>> NumberToName.convert(53) 
'A0' 
>>> NumberToName.convert(1692) 
'_1' 
>>> NumberToName.convert(23893) 
'FAQ' 

Sfortunatamente, questi numeri devono essere associati a questi nomi esatti (per consentire una conversione inversa).

---

Nota: un numero variabile di bit viene ricevuto e convertito in un numero senza ambiguità. Questo numero deve essere convertito in modo non ambiguo in un nome nello spazio dei nomi dell'identificatore Python. Alla fine, i nomi Python validi saranno convertiti in numeri e questi numeri saranno convertiti in un numero variabile di bit.

---

soluzione finale:

import string 

HEAD_CHAR = ''.join(sorted(string.ascii_letters + '_')) 
TAIL_CHAR = ''.join(sorted(string.digits + HEAD_CHAR)) 
HEAD_BASE, TAIL_BASE = len(HEAD_CHAR), len(TAIL_CHAR) 

def convert_number_to_name(number): 
    if number < HEAD_BASE: return HEAD_CHAR[number] 
    q, r = divmod(number - HEAD_BASE, TAIL_BASE) 
    return convert_number_to_name(q) + TAIL_CHAR[r] 

Answer 1

Si tratta di un piccolo problema di divertimento pieno di fuori di 1 errori.

Senza loop:

import string 

first_digits = sorted(string.ascii_letters + '_') 
rest_digits = sorted(string.digits + string.ascii_letters + '_') 

def convert(number): 
    if number < len(first_digits): 
     return first_digits[number] 

    current_base = len(rest_digits) 
    remain = number - len(first_digits) 
    return convert(remain/current_base) + rest_digits[remain % current_base] 

E le prove:

print convert(0) 
print convert(26) 
print convert(52) 
print convert(53) 
print convert(1692) 
print convert(23893) 

uscita:

A 
_ 
z 
A0 
_1 
FAQ 

Answer 2

È possibile utilizzare il codice in this risposta alla domanda "Base 62 di conversione in Python" (o forse una delle altre risposte).

Utilizzando il codice di riferimento, credo che la risposta vostro vera domanda che era "come può il nome essere calcolato in base al numero senza memorizzare una cache?" sarebbe quello di rendere il nome la semplice conversione di base 62 del numero eventualmente con un trattino basso principale se il primo carattere del nome è una cifra (che viene semplicemente ignorata quando si riconvertisce il nome in un numero).

Ecco il codice di esempio che illustrano ciò che vi propongo:

from base62 import base62_encode, base62_decode 

def NumberToName(num): 
    ret = base62_encode(num) 
    return ('_' + ret) if ret[0] in '' else ret 

def NameToNumber(name): 
    return base62_decode(name if name[0] is not '_' else name[1:]) 

if __name__ == '__main__': 
    def test(num): 
     name = NumberToName(num) 
     num2 = NameToNumber(name) 
     print 'NumberToName({0:5d}) -> {1!r:>6s}, NameToNumber({2!r:>6s}) -> {3:5d}' \ 
       .format(num, name, name, num2) 

    test(26) 
    test(52) 
    test(53) 
    test(1692) 
    test(23893) 

uscita:

NumberToName( 26) -> 'q', NameToNumber( 'q') -> 26 
NumberToName( 52) -> 'Q', NameToNumber( 'Q') -> 52 
NumberToName( 53) -> 'R', NameToNumber( 'R') -> 53 
NumberToName(1692) -> 'ri', NameToNumber( 'ri') -> 1692 
NumberToName(23893) -> '_6dn', NameToNumber('_6dn') -> 23893 

Se i numeri potrebbero essere negativi, potrebbe essere necessario modificare il codice dalla risposta di riferimento (e non v'è qualche discussione lì su come farlo).

Answer 3

testati per i primi 10.000 nomi:

first_chars = sorted(string.ascii_letters + '_') 
later_chars = sorted(list(string.digits) + first_chars) 

def f(n): 
    # first, determine length by subtracting the number of items of length l 
    # also determines the index into the list of names of length l 
    ix = n 
    l = 1 
    while ix >= 53 * (63 ** (l-1)): 
     ix -= 53 * (63 ** (l-1)) 
     l += 1 

    # determine first character 
    first = first_chars[ix // (63 ** (l-1))] 

    # rest of string is just a base 63 number 
    s = '' 
    rem = ix % (63 ** (l-1)) 
    for i in range(l-1): 
     s = later_chars[rem % 63] + s 
     rem //= 63 

    return first+s 

Answer 4

Quello che hai è una forma corrotta di bijective numeration (l'esempio solita essere nomi di colonne foglio di calcolo, che sono biunivoca base-26).

Un modo per generare numerazione biunivoca:

def bijective(n, digits=string.ascii_uppercase): 
    result = [] 
    while n > 0: 
     n, mod = divmod(n - 1, len(digits)) 
     result += digits[mod] 
    return ''.join(reversed(result)) 

Tutto quello che dovete fare è fornire un diverso insieme di cifre per il caso in cui 53 >= n > 0. Sarà inoltre necessario incrementare n da 1, come correttamente il biunivoca 0 è la stringa vuota, non "A":

def name(n, first=sorted(string.ascii_letters + '_'), digits=sorted(string.ascii_letters + '_' + string.digits)): 
    result = [] 
    while n >= len(first): 
     n, mod = divmod(n - len(first), len(digits)) 
     result += digits[mod] 
    result += first[n] 
    return ''.join(reversed(result))