기수 정렬을 위해 문자열을 숫자로 변환 (구문 분석하지 않음)

Question

다른 정렬 알고리즘으로 모든 종류의 데이터 유형을 정렬해야하는 학교 프로젝트가 있습니다. 기수 정렬은 잘 작동하지만 정수 이외의 것은 정렬 할 수 없습니다. 모든 데이터 유형이 정수로 정렬되기 때문에 정수 이외의 다른 정렬 결과를 추가하지는 않을 것입니다.

그렇습니다. 문자열을 정수로 변환하는 더 좋은 방법이 있는지 알고 싶습니다. 여기 나와 함께. 파이썬을 능가하지 않으려 고 가능한 한 표준 함수를 사용하려고했습니다.

def charToHex(char): 
    return hex(ord(char))[2:] 

def stringToHex(text): 
    t = '' 
    for char in text: 
     t += charToHex(char) 

    return t 

def stringToInt(text): 
    return int(stringToHex(text), 16) 

print stringToInt('allo') 
print stringToInt('allp') 
print stringToInt('all') 

잘 작동하지만 더 좋은 방법이 있는지 알고 싶습니다. 그것이 가치있는 일이라면, 기수 정렬과 정수 이외의 다른 것을 정렬하는 것은 무의미한 소리가됩니다. 왜냐하면 정수 목록을 정렬 할 수 있기 때문입니다. 모든 키의 값을 다시 목록으로 가져와야합니다.

나는 그런 식으로 생각하고 있었다. 내 목록의 각 값에 대해 정수 키를 가져옵니다. 해당 키를 해시 테이블에 넣고 해당 해시 테이블의 목록에 값을 넣습니다. 목록의 값을 정수 키로 바꾸고 키 목록을 정렬하십시오.

정렬 된 목록의 각 키에 대해 해당 키의 값 목록을 가져 와서 한 항목을 팝합니다. 해당 항목을 목록에 넣고 계속하십시오.

변환을 필요로하지 않는 다른 정렬 대신 기수 정렬을 사용하여이 프로세스를 최적화 할 수있는 방법이 있는지 알고 싶습니다. 목록에있는 항목의 금액은 실제로 여기에 코드가 서로 다른 크기의 문자열이 작동하지 않습니다 50000

편집

넘어 갈 수 있습니다. 나는 그걸 확인하는 방법을 잘 모르겠다. 문자열을 스페이스로 채우는 것이 효과가있는 것 같습니다.

def getMaxLen(ls): 
    lenght = 0 

    for text in ls: 
     lenght = max(lenght, len(text)) 

    return lenght 

def convertList(ls): 
    size = getMaxLen(ls) 
    copy = ls[:] 

    for i, val in enumerate(copy): 
     copy[i] = stringToInt(val.ljust(size, ' ')) 

    return copy 

print convertList(["allo", "all", "bal"]) 

Answer 1

먼저, this article을 살펴보십시오. 이 기사는 네, 어떤 경우에는 다른 정렬보다 빠른 문자열에 대한 기수 정렬 알고리즘을 이해할 수 있음을 보여줍니다.

둘째, 더 중요한 것은 조기 최적화를 수행하고 있는지 물어볼 것입니다. 파이썬의 sort() 함수로 50k 항목을 정렬하는 것은 엄청나게 빠를 것입니다. 응용 프로그램에서 이것이 병목 현상이라고 확신하지 않는다면 걱정하지 않고 그냥 sort() 기능을 사용합니다. 병목 현상이있는 경우 이러한 종류의 모든 작업 (예 : 캐싱, 정렬되지 않은 데이터에서 작동하는 알고리즘 등)을 수행하지 않아도 될 수 없는지 확인해야합니다.