acmpesuecc / acmpesuecc/traffic_simulation

Data Structure Alternatives - Commenting on efficiency

オープン
#8 コメント 46 件 リアクション 0 件 担当者 1 名 @sameermanvi が担当を希望しています GitHub で見る
BOUNTY:75 hacknight-2025 hacktoberfest
主要言語
Python
スター
1
フォーク
13
PR マージ指標
30日以内にマージされた PR はありません

説明

# Bounty Points: 75

## Branch Instructions
push changes to a new *'ds'* branch

***

**Explanation:**

Current clock list management is **inefficient**
Removes items while iterating: `for i in clock: if i[2]==t: clock.remove(i)`
$O(n^2)$ complexity due to `list.remove()` in loop
No priority queue for event scheduling

Current problematic code:
```python
for i in clock:
if i[2] == t:
clock.remove(i) # $O(n)$ operation in $O(n)$ loop
```
### Possible fix/approach:

* Replace list with **`heapq`**-based **priority queue**
* Use event-based scheduling with `(time, event\_data)`
* Alternative: **dictionary** with time as key
* Benchmark before/after improvements
* Document complexity improvements

---

### Maintainer notes:

* Current approach causes **performance issues** with large graphs
* Focus on **clock/event management data structure**
* Should maintain same simulation logic

---

### Resources:

* Python `heapq` documentation
* Event-driven simulation patterns

---

コントリビューションガイド

コントリビューションガイドを開く

評価

この issue はまだ評価されていません。

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。