acmpesuecc / acmpesuecc/traffic_simulation
Data Structure Alternatives - Commenting on efficiency
- Ngôn ngữ chính
- Python
- Star
- 1
- Fork
- 13
- Chỉ số merge pull request
- Không có pull request nào được merge trong 30 ngày
Mô tả
# 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
---
Hướng dẫn đóng góp
Đánh giá
Issue này chưa được đánh giá.