table.sort는 어떤 알고리즘을 사용합니까?

나는 궁금해서 그것이 내가 건너 한 다른 정렬 알고리즘보다 느린 유일하기 때문에 어떤 알고리즘 루아의 기본 table.sort 용도. 루아의 table.sort이 C로 엔진에 쓰여 있거나 루아의 라이브러리에 있다면 궁금합니다.table.sort는 어떤 알고리즘을 사용합니까?

출처

2013-08-04 jocopa3

어떤 알고리즘을 사용 table.sort합니까?

comment in tablib.c은 (조금 스크롤)

/* 
** {====================================================== 
** Quicksort 
** (based on `Algorithms in MODULA-3', Robert Sedgewick; 
** Addison-Wesley, 1993.) 
** ======================================================= 
*/

당신은 내가 제공된 링크에서 소스 코드를 읽을 수있는 상태.

Lua의 table.sort가 C로 작성되거나 Lua의 라이브러리에있는 경우 궁금합니다. 이 때

는 루아와 직접 와서 모든 라이브러리 ( io, table, math는 ...) table.sort이 퀵을 사용

출처

2013-08-04 14:17:57 Oberon

LuaJIT는 [smoothsort] (http://en.wikipedia.org/wiki/Smoothsort) 로의 전환을 고려하고 있으며, 라이브러리 함수 중 몇 가지가 이제 Lua 바이트 코드로 구현되었다는 점에 유의하십시오 (이는 실제로 유용합니다. JIT가 더 잘 컴파일 됨) –

내부적으로 C로 작성되어, 그것은 C. 참고로 작성 그 퀵 소트는 안정적이지 않아. 놀랍게도 루아는 C의 qsort()을 직접 사용하지 않았습니다. 성능에 관해서는

, 그것은 다양한 요소가 있기 때문에, 예를 들어 이야기하기 어렵다, 어떤 언어 어떤 알고리즘 당신이 비교하고, 데이터의 종류를 테스트하고있다.

출처

2013-08-04 14:18:27

루아를 사용하면, 기본값보다 약간 더 빠른 알고리즘을 발견했습니다. 적절하게 크기가 작 으면 칵테일 정렬과 버블 정렬은 실제로 기본값보다 빠릅니다. 크기가 크다면 LSD 기수 정렬은 내가 말한 다른 두 가지와 함께 빠릅니다. 나는 반전 된 배열, 무작위 배열 및 대부분 정렬 된 배열과 같은 다른 유형의 데이터로 테스트하고 있지만 각 테스트에서 기본 정렬은 조금 느리다. – jocopa3

@ jocopa3 내가보기에 이것은 루아의 문제가 아니라 오히려 quicksort의 문제입니다. 예 : quicksort는 정렬 된 배열과 역순 배열에서 제대로 수행되지 않습니다. 특정 문제에 대한 정렬 작업이 필요하고 루아의 기본 정렬이 제대로 작동하지 않는다면 C에서 특정 정렬 알고리즘을 직접 작성하는 것이 좋습니다. –

@YuHao 링크 된 소스를 살펴볼 때마다 루아의 qsort가 중간을 피벗으로 선택합니다. 그것은 qsort의 이상적인 경우에 가까워 야하며 성능이 좋지 않아야합니다. 나는 모든 lua API 호출이 느려지는 것일 수도 있지만 그것이 프로파일 링되지 않는 한 확신 할 수는 없다고 생각합니다. – greatwolf

table.sort는 어떤 알고리즘을 사용합니까?

답변

관련 문제