정렬 알고리즘에 대한 비교 기반으로 정렬 문제입니까?
https://stackoverflow.com/questions/297035
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
나는 현재 직면하는 어려운 정렬 문제입니다.나의 컬렉션이 있는 이벤트 정렬할 필요가 서로에 대한(a 비교를 정렬 다)및 그들의 상대적인 위치는 목록에 있습니다.
간단히 말해서 내가 있는 이벤트의 목록을 각각 우선 순위(integer),기간(초 단위),그 최초 발생 시간에는 이벤트 목록에 표시 할 수 있습니다.내가 필요로 정렬하는 이벤트가 우선 순위에 따라,그러나 없는 이벤트에 나타날 수 있 목록하기 전에 그 최초 발생 시간입니다.여기에 예를(아마)분석하는:
// Psuedo C# code
class Event { int priority; double duration; double earliestTime ; }
void Example()
{
Event a = new Event { priority = 1, duration = 4.0, earliestTime = 0.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 6.0 };
Event c = new Event { priority = 3, duration = 3.0, earliestTime = 0.0 };
Event d = new Event { priority = 4, duration = 2.0, earliestTime = 0.0 };
// assume list starts at 0.0 seconds
List<Event> results = Sort( new List<Event> { a, b, c, d } );
assert( results[ 0 ] == a ); // 4.0 seconds elapsed
assert( results[ 1 ] == c ); // 7.0 seconds elapsed
assert( results[ 2 ] == b ); // 12.0 seconds elapsed
assert( results[ 3 ] == d ); // 14.0 seconds elapsed
}
품목"b"와서 마지막 때문에 그것이 허용되지 않습을 시작할 때까지 6.0 초으로 목록은,그래서 그것은 지연된"c"하기 위해 도착하기 전에"b"비록 우선순위가 낮습니다.(희망을 상기 설명 나의 문제가하지 않을 경우,나를 알고 내가 편집할 수 있습니다.)
현재 아이디어가 사용하는 삽입 정렬 을 관리하 정렬 과정입니다.리의 다른 일반적인 정렬 알고리즘,삽입 정렬 순서를 결정의 목록을 한 번에 하나기 위해서.그래서 각 지수는 나을 찾을 수 있어야합니다 다음으로 낮은 우선순위가 행사의 초기발생 시간을 만족하실 것입니다.
나를 찾으려는 자원에 대해 정렬 알고리즘과 데이터 구조는 데 도움이 나는 디자인에 대한 좋은 해결책이"종류"의 문제입니다.나의 진짜 문제는 실제로는 이보다 더 복잡:계층적 분류,변 버퍼 사이의 이벤트,여러 non-지속적인 시간의 제약,그래서 더 많은 정보 또는 아이디어가 더 나은입니다.속도와 공간은 정말로 관심사입니다.정확성에 정렬하고 유지 관리의 코드는 관심사입니다.
편집: 설명(에 기반한 의견)
- 이벤트 소의 전체 기간(는 없이 겹치는 이벤트의 허용)
- 이벤트 야 에서 발생 또는 후에 그들의 earliestTime 할 수 없습니다 발생하기 전에 자신의 earliestTime.
- 이벤트 발생할 수 있습보다 나중에 그들의 earliestTime 는 경우 우선순위가 낮은 존재 이벤트
- 이벤트 중단할 수 없
- 최대가 기간의 합계는 모든 이벤트에 맞출 수 있습니다.이것은 다음과 같다.(현실에서는 기간의 모든 이벤트보다 훨씬 더 큰 것입 시간 목록의 최대의 기간이 있습니다.)
- 할 수는 없다.(구멍이 없을 시도하고 다시 입력합니다.)
편집: 응답
는 동안 데이비드 Nehme 게 답을 선택하고 싶어하는 것을 지적한 그의 대답은 삽입 종류에 마음,그리고 여러 가지 다른 사람들이 제공하는 삽입 정렬 입력 답변이 있습니다.이를 통해 나는 전문 삽입 정렬 아마도 갈 수있는 방법입니다.여러분 모두에게 감사드립니다 당신의 답변이 있습니다.
해결책
이것은 실제로 분류 문제 이상입니다. 릴리스 날짜와 관련된 단일 기계 스케줄링 문제입니다. 당신이하려는 일에 따라 문제는 NP-Hard 일 수 있습니다. 예를 들어, 완료 시간의 가중량을 모방하려고한다면 (우선 순위에 반비례하는 가중치) 문제는 다음과 같습니다. 분류 ~처럼
1|ri;pmtn|Σ wiCi
그리고 NP-Hard입니다. 많은 것이 있습니다 서류 이 주제에서는 필요한 것보다 더 많을 수 있습니다.
귀하의 경우, 간격이있는 솔루션을 원하지 않으므로 간단한 개별 이벤트 시뮬레이션 (O (N Log (N))) 시간입니다. Released_Jobs를 우선 순위 대기열로 저장해야합니다.
unreleased_jobs = jobs // sorted list of jobs, by release date
released_jobs = {} // priority queue of jobs, by priority
scheduled_jobs = {} // simple list
while (!unreleased_jobs.empty() || !released_jobs.empty()) {
while (unreleased_jobs.top().earliestTime <= t) {
released_jobs.push(unreleased_jobs.pop())
}
if (!released_jobs.empty()) {
next_job = released_jobs.pop();
scheduled_jobs.push_back(next_job)
t = t + next_job.duration
} else {
// we have a gap
t = unreleased_jobs.top().earliestTime
}
}
한 가지 문제는 우선 순위가 짧고 우선 순위가 높은 직무 직전에 릴리스 시간이 낮은 우선 순위가 낮을 수 있지만, 간격이없는 경우 (간격이없는 일정이 가능한 경우) 속성이있는 일정을 제시한다는 것입니다. .
다른 팁
즉,최적화하려는 전반적인 시간을 실행하는 동안 수립 두 가지 조건(강:는 가장 빠른 시점의 실행 약한:우선 순위)?이 제약 조건을 만족 문제.있는 특별한 해법에 대해 이런 종류의 문제입니다.
또한,jakber 의 솔루션을 작동하지 않습니다.지 않고도 기간 동안,다음 예제를 분명히 실패하면:
event a (priority = 1, start = 5)
event b (priority = 2, start = 0)
정렬 순 것 a, b 는 동안 원하는 결과가 확실 b, a.
제 생각에는:
- 우선 순위별로 작업을 정렬합니다
- 초기 시간이 지난 후 최초의 사용 가능한 슬롯을 취하는 작업을 타임 라인에 맞추면 작업에 충분히 큰 구멍이 있습니다.
타임 라인을 목록으로 변환하여 작업을 기다렸다가 간격을 기다립니다.
질문:
- 간격이 허용됩니까?
- 작업을 분할 할 수 있습니까?
- 질문에서와 같이 작업을 감안할 때 : B를 완성하기 위해 B를 지연시키는 것이 더 낫습니까?
편집하다:
OS 내 질문에 대한 답은 다음과 같습니다.
- 아니오 (ISH- 실행할 것이 없다면 우리는 간격을 가질 수있을 것 같아요)
- 아니
- 아직 명확하지 않지만이 예제는 실행 C와 지연 b를 제안합니다.
이 경우 알고리즘은 다음과 같습니다.
- 우선 순위별로 정렬하십시오
- t = 0부터 시작하는 현재 '시간'에 대한 카운터를 유지하십시오.
- T에서 시작할 수있는 가장 높은 우선 순위 항목에 대해 정렬 된 목록을 검색하십시오.
- 런닝 순서에 항목을 추가하고 기간을 T에 추가하십시오.
- 목록이 소진 될 때까지 3 & 4를 반복하십시오. T에서 실행할 수있는 작업이없고 보류중인 작업이 남아있는 경우 1 초 수면 작업을 실행 순서로 고정하십시오.
이 알고리즘도 O (n^2)입니다.
나는 당신이 목록을 두 번 정렬해야한다고 생각합니다. 우선 우선 순위에 따라 그리고 초기에는 안정적인 예를 들어 삽입 정렬과 같은 정렬 알고리즘. 그렇게하면 시간이 증가하고 매번 사물이 우선 순위에 따라 정렬됩니다.
당신이 무언가를 보지 않는 한, 당신은 종류의 목적으로 각 이벤트의 지속 시간을 완전히 무시할 수 있습니다.
우선 순위 수준 세트가 제한된 경우 각 레벨마다 1 세트의 목록 세트를 유지할 수 있습니다. 다음 이벤트가 필요할 때마다 시작 시간이 통과 된 사람을 찾을 때까지 각 목록의 헤드를 우선 순위로 확인하십시오. (확인하는 동안 최소 시작 시간을 추적하십시오 - 아직 이벤트가 준비되지 않은 경우 어느 쪽을 기다릴지 알고 있습니다)
내가 다른 날에 가지고 있었던 문제처럼 들린다. 여기.
C#을 사용하고 있다고 가정하면 ...
또한 가장 일반적인 경우에는 해결책이 없을 수 있습니다 (Douglas가 지적했듯이 간격이 허용되지 않는 한). 예를 들어:
Event a = new Event { priority = 1, duration = 1.0, earliestTime = 4.0 };
Event b = new Event { priority = 2, duration = 1.0, earliestTime = 4.0 };
Event c = new Event { priority = 3, duration = 1.0, earliestTime = 4.0 };
Event d = new Event { priority = 4, duration = 1.0, earliestTime = 4.0 };
나는 당신의 문제의 복잡성을 이해하는 것이 확실하지 않지만, 나의 본능은 당신이 우선 순위와 시작 시간의 관계를 정의해야한다고 말합니다. 예는 다음과 같습니다.
Event a = new Event { priority = 1, duration = 4.0, earliestTime = 1.0 };
Event b = new Event { priority = 2, duration = 5.0, earliestTime = 0.0 };
그래서 우리는 계속해서 시작합니까? b 시간 = 0, 아니면 진드기를 기다린 다음 시작합니까? a 우선 순위가 높기 때문에? 더 많은 우선 순위와 더 긴 시간 트레이드 오프가있는 더 많은 이벤트가 있다고 가정 해 봅시다. "다음 이벤트가 x 더 높고 갭 (지금과 초기 사이의 초기 사이)이 y 초 미만인 경우, 우선 순위가 높은 이벤트를 시작한 다음 우선 순위가 낮은 선을 따라 규칙이 필요하다고 생각합니다. 그렇지 않으면 우선 순위가 낮습니다. 이벤트 (따라서 우선 순위가 높은 우선 순위를 뒤로 밀기) ".
다음은 Douglas의 답변 라인을 따라 일부 Python 코드입니다. 먼저 우선 순위별로 정렬 한 다음 선택 소트 방식으로 타임 라인을 맞 춥니 다.
#!/usr/bin/env python
MIN_PRIORITY = 100
class Event(object):
def __init__(self, name, priority, duration, earliestTime):
self.name = name
self.priority = priority
self.duration = duration
self.earliestTime = earliestTime
def __str__(self):
return "%-10s: P %3d D %3.1f T %3.1f" % (self.name, self.priority, self.duration, self.earliestTime)
def sortEvents(_events):
def comparePriority(event1, event2):
if event1.priority < event2.priority: return -1
if event1.priority > event2.priority: return 1
return 0
# Get a copy of the events and sort by priority
events = [e for e in _events]
events.sort(cmp=comparePriority)
# Select one event at a time, checking for compatibility with elapsed time
elapsedTime = 0.0
sortedEvents = []
while events:
minGap = events[0].earliestTime - elapsedTime
for e in events:
currentGap = e.earliestTime - elapsedTime
if currentGap < minGap:
minGap = currentGap
if currentGap <= 0.0:
sortedEvents.append(e)
elapsedTime += e.duration
events.remove(e)
break
# If none of the events fits, add a suitable gap
if minGap > 0:
sortedEvents.append( Event("gap", MIN_PRIORITY, minGap, elapsedTime) )
elapsedTime += minGap
return sortedEvents
if __name__ == "__main__":
#e1 = Event("event1", 1, 1.0, 4.0)
#e2 = Event("event2", 2, 1.0, 6.0)
#e3 = Event("event3", 3, 1.0, 8.0)
#e4 = Event("event4", 4, 1.0, 10.0)
e1 = Event("event1", 1, 4.0, 0.0)
e2 = Event("event2", 2, 5.0, 6.0)
e3 = Event("event3", 3, 3.0, 0.0)
e4 = Event("event4", 4, 2.0, 0.0)
events = [e1, e2, e3, e4]
print "Before:"
for event in events: print event
sortedEvents = sortEvents(events)
print "\nAfter:"
for event in sortedEvents: print event
실제로 비교 기반 정렬을 원한 것 같습니다. 정렬 키는 해당 순서대로 {초기 시간, 우선 순위}입니다. 예제는 pseudo-c#이므로 pseudo-c# 솔루션을 제공하겠습니다.
class Event : IComparable<Event>, IComparable{
int priority;
double duration;
double earliestTime;
public int CompareTo(Event other){
if(other == null)
return 1; /* define: non-null > null */
int cmp = earliestTime.CompareTo(other.earliestTime);
if(cmp != 0)
return cmp;
/* earliestTimes were equal, so move on to next comparison */
return priority.CompareTo(other.priority);
}
int IComparable.CompareTo(object other){ /* for compatibility with non-generic collections */
if(other == null)
return 1; /* define: non-null > null */
Event e_other = other as Event;
if(e_other == null) /* must have been some other type */
throw new ArgumentException("Must be an Event", "other");
return CompareTo(e_other); /* forward to strongly-typed implementation */
}
}
이제 귀하의 목록은 귀하의 주장이 기대하는대로 정렬됩니다.
편집하다:
나의 첫 번째 추정은 이벤트가 목록에서 뽑히고 별도의 스레드로 나눠서 다음 이벤트가 정시에 다음 이벤트를 해고 할 수 있도록 이벤트가 별도의 스레드로 전달 될 것이라는 것이었다. 단일 스레드는 여전히 높은 우선 순위 이벤트가 시작 시간에 가능한 한 가깝게 발사 할 수있게 해주었습니다. 이 경우 CompareTo 기능은 다음과 같이 변경되어야합니다.
public int CompareTo(Event other){
if(other == null)
return 1; /* define: non-null > null */
int cmp = priority.CompareTo(other.priority);
if(cmp == 0)
/*
* calculate and compare the time each event will be late
* if the other one were to start first. This time may be
* negative if starting one will not make the other one late
*/
return (earliestTime + duration - other.earliestTime).CompareTo(
other.earliestTime + other.duration - earliestTime);
/*
* they're different priorities. if the lower-priority event
* (presume that greater priority index means lower priority,
* e.g. priority 4 is "lower" priority than priority 1), would
* would make the higher-priority event late, then order the
* higher-priority one first. Otherwise, just order them by
* earliestTime.
*/
if(cmp < 0){/* this one is higher priority */
if(earliestTime <= other.earliestTime)
/* this one must start first */
return -1;
if(other.earliestTime + other.duration <= earliestTime)
/* the lower-priority event would not make this one late */
return 1;
return -1;
}
/* this one is lower priority */
if(other.earliestTime <= earliestTime)
/* the other one must start first */
return 1;
if(earliestTime + duration <= other.earliestTime)
/* this event will not make the higher-priority one late */
return -1;
return 1;
}
어떤 가정에서도 이것을 테스트하지만 그것이 우리가 찾고있는 것이라고 생각합니다.
