# Built-in collections are simple but not optimized
my_list = [1, 2, 3, 4, 5]
my_dict = {"a": 1, "b": 2}
my_set = {1, 2, 3, 4, 5}

# What happens when you need:
# - Sorted data with fast insertion?
# - Immutable structures for functional programming?
# - Memory-efficient operations on large datasets?
# - Specialized data patterns (priority queues, tries, etc)?

# Naive approach - terrible performance
sorted_list = []
for item in data:
    sorted_list.append(item)
    sorted_list.sort()  # O(n log n) every time!

# Better approach with specialized library
from sortedcontainers import SortedList
sorted_list = SortedList()
for item in data:
    sorted_list.add(item)  # O(log n) - much better!

# Mutable collections can cause bugs
def process_data(items):
    items.append("processed")  # Oops! Modified original
    return items

original = [1, 2, 3]
result = process_data(original)
# original is now [1, 2, 3, "processed"] - unexpected!

# Immutable approach
from pyrsistent import v
original = v(1, 2, 3)
result = original.append("processed")  # Returns new collection
# original is still v(1, 2, 3) - safe!

# Naive approach - scan everything
def autocomplete_naive(words, prefix):
    return [word for word in words if word.startswith(prefix)]
# O(n * m) where n=words, m=average word length

# Trie approach - follow path
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

def autocomplete_trie(trie, prefix):
    # O(p + k) where p=prefix length, k=results
    # Much faster for large word lists

# Memory layout: [item1][item2][item3][item4]...
# Pros: Cache-friendly, fast iteration
# Cons: Insertion/deletion can be expensive

# Memory layout: Nodes with pointers
# Pros: O(log n) insertion/deletion
# Cons: Poor cache locality, pointer overhead

# Small data (< 1,000 items): Built-ins usually fine
small_data = list(range(1000))
# Performance differences minimal

# Medium data (1,000 - 100,000 items): Specialized collections shine
medium_data = list(range(100000))
# 10-100x performance differences possible

# Large data (> 100,000 items): Library choice critical
large_data = list(range(1000000))
# Can mean difference between seconds and hours

# sortedcontainers (pure Python) vs bintrees (C extension)
# sortedcontainers wins by 10x+ in many operations
# How? Better algorithms + cache-friendly data structures

# Copying mutable collection
new_dict = old_dict.copy()  # O(n) copy operation
new_dict['key'] = 'value'

# Immutable with structural sharing
new_pmap = old_pmap.set('key', 'value')  # O(log n), shares structure

# sortedcontainers - drop-in replacement
from sortedcontainers import SortedList
sl = SortedList([1, 3, 5])
sl.add(4)  # Maintains sorted order automatically

# pyrsistent - similar to built-ins
from pyrsistent import m
data = m(a=1, b=2)
new_data = data.set('c', 3)  # Immutable update

# Product ranking system
products = millions_of_products

# Naive approach: Re-sort entire list when score changes
# O(n log n) per update - unusable at scale

# sortedcontainers approach: Maintain sorted order
# O(log n) per update - real-time updates possible
from sortedcontainers import SortedList
rankings = SortedList(products, key=lambda p: p.score)

# Player scores need constant updates
players = SortedList(key=lambda p: -p.score)  # Descending order

# O(log n) to add new score
# O(log n) to update existing score
# O(k) to get top-k players
# Enables real-time leaderboard updates

# Buy/sell orders sorted by price
buy_orders = SortedList(key=lambda o: -o.price)   # Highest first
sell_orders = SortedList(key=lambda o: o.price)   # Lowest first

# O(log n) to add orders
# O(1) to get best bid/ask
# Critical for low-latency trading

# LRU cache with size limits
from collections import OrderedDict

class LRUCache:
    def __init__(self, maxsize):
        self.cache = OrderedDict()
        self.maxsize = maxsize

    def get(self, key):
        if key in self.cache:
            # Move to end (most recent)
            self.cache.move_to_end(key)
            return self.cache[key]
        return None

    def set(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        elif len(self.cache) >= self.maxsize:
            # Remove oldest
            self.cache.popitem(last=False)
        self.cache[key] = value

from sortedcontainers import SortedList, SortedDict, SortedSet

import polars as pl  # The future of dataframes

from pyrsistent import pvector, pmap, pset

import cytoolz as toolz  # Always use cytoolz over toolz

import more_itertools as mit

# From dict to SortedDict
from sortedcontainers import SortedDict

# Before
d = dict()
d[key] = value
sorted_items = sorted(d.items())

# After
sd = SortedDict()
sd[key] = value
sorted_items = list(sd.items())  # Already sorted

# Memory-efficient categorical data
import pyarrow as pa

# Instead of storing repeated strings
strings = ['category_a'] * 1000000

# Use dictionary encoding
dict_array = pa.array(strings).dictionary_encode()
# Can achieve 50x+ memory reduction

from collections import deque
import threading

# Thread-safe operations on deque
d = deque()

# These operations are atomic
d.append(item)        # Thread-safe
d.appendleft(item)    # Thread-safe
item = d.pop()        # Thread-safe
item = d.popleft()    # Thread-safe

from sortedcontainers import SortedList
from collections import namedtuple

PlayerScore = namedtuple('PlayerScore', ['score', 'player_id', 'timestamp'])

class Leaderboard:
    def __init__(self, max_size=10000):
        # Reverse order for highest scores first
        self.scores = SortedList(key=lambda x: -x.score)
        self.max_size = max_size

    def add_score(self, player_id, score):
        entry = PlayerScore(score, player_id, time.time())
        self.scores.add(entry)

        # Maintain size limit
        if len(self.scores) > self.max_size:
            self.scores.pop()

    def get_top_k(self, k=10):
        return list(self.scores[:k])

    def get_player_rank(self, player_id, score):
        entry = PlayerScore(score, player_id, 0)
        return self.scores.bisect_left(entry) + 1

import heapq
from collections import defaultdict

class HighFrequencyLeaderboard:
    """For ultra-low latency scenarios"""
    def __init__(self, top_k=100):
        self.heap = []  # Min-heap for top K
        self.k = top_k
        self.player_scores = defaultdict(float)

    def update_score(self, player_id, score):
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, (score, player_id))
        elif score > self.heap[0][0]:
            heapq.heapreplace(self.heap, (score, player_id))

        self.player_scores[player_id] = score

from pyrsistent import PClass, field, pvector, pmap
from typing import Optional

class DatabaseConfig(PClass):
    host = field(type=str, mandatory=True)
    port = field(type=int, factory=lambda: 5432)
    database = field(type=str, mandatory=True)
    ssl_mode = field(type=str, factory=lambda: "prefer")

    def connection_string(self):
        return f"postgresql://{self.host}:{self.port}/{self.database}?sslmode={self.ssl_mode}"

class AppConfig(PClass):
    debug = field(type=bool, factory=lambda: False)
    database = field(type=DatabaseConfig, mandatory=True)
    cache_ttl = field(type=int, factory=lambda: 3600)
    features = field(type=pvector, factory=pvector)

    def with_overrides(self, **overrides):
        """Create new config with overrides applied"""
        return self.set(**overrides)

# Configuration hierarchy implementation
class ConfigHierarchy:
    def __init__(self):
        self.layers = pvector([])

    def add_layer(self, config_dict, priority=0):
        """Add configuration layer with priority"""
        layer = (priority, pmap(config_dict))
        # Insert maintaining sort order
        self.layers = self.layers.append(layer).sort(key=lambda x: x[0])

    def resolve(self):
        """Merge all layers with higher priority winning"""
        result = {}
        for priority, config in self.layers:
            result.update(config)
        return pmap(result)

from collections import OrderedDict
from threading import RLock
from typing import Any, Optional, Callable
import time

class ThreadSafeLRUCache:
    def __init__(self, capacity: int, ttl: Optional[float] = None):
        self.capacity = capacity
        self.ttl = ttl
        self.cache = OrderedDict()
        self.timestamps = OrderedDict() if ttl else None
        self.lock = RLock()
        self.hits = 0
        self.misses = 0

    def get(self, key: Any) -> Optional[Any]:
        with self.lock:
            if self._is_expired(key):
                self._remove(key)
                self.misses += 1
                return None

            if key in self.cache:
                # Move to end (most recently used)
                value = self.cache.pop(key)
                self.cache[key] = value
                if self.timestamps:
                    timestamp = self.timestamps.pop(key)
                    self.timestamps[key] = timestamp
                self.hits += 1
                return value

            self.misses += 1
            return None

    def set(self, key: Any, value: Any) -> None:
        with self.lock:
            current_time = time.time() if self.ttl else None

            if key in self.cache:
                # Update existing
                self.cache.pop(key)
                if self.timestamps:
                    self.timestamps.pop(key)
            elif len(self.cache) >= self.capacity:
                # Evict least recently used
                oldest_key, _ = self.cache.popitem(last=False)
                if self.timestamps:
                    self.timestamps.pop(oldest_key, None)

            self.cache[key] = value
            if self.timestamps:
                self.timestamps[key] = current_time

    def _is_expired(self, key: Any) -> bool:
        if not self.ttl or not self.timestamps:
            return False

        timestamp = self.timestamps.get(key)
        if timestamp is None:
            return True

        return time.time() - timestamp > self.ttl

    def _remove(self, key: Any) -> None:
        self.cache.pop(key, None)
        if self.timestamps:
            self.timestamps.pop(key, None)

    def stats(self) -> dict:
        total = self.hits + self.misses
        hit_rate = self.hits / total if total > 0 else 0
        return {
            'hits': self.hits,
            'misses': self.misses,
            'hit_rate': hit_rate,
            'size': len(self.cache),
            'capacity': self.capacity
        }

from functools import lru_cache, wraps
import asyncio

def async_lru_cache(maxsize=128):
    """LRU cache for async functions"""
    def decorator(func):
        # Create sync version for caching
        cache = lru_cache(maxsize=maxsize)(lambda *args, **kwargs: None)

        @wraps(func)
        async def wrapper(*args, **kwargs):
            # Check cache
            cache_key = (args, tuple(sorted(kwargs.items())))

            # Simple async cache implementation
            if not hasattr(wrapper, '_cache'):
                wrapper._cache = {}

            if cache_key in wrapper._cache:
                return wrapper._cache[cache_key]

            # Compute and cache
            result = await func(*args, **kwargs)

            # Maintain size limit
            if len(wrapper._cache) >= maxsize:
                # Remove oldest (simple FIFO for demonstration)
                oldest_key = next(iter(wrapper._cache))
                del wrapper._cache[oldest_key]

            wrapper._cache[cache_key] = result
            return result

        wrapper.cache_info = cache.cache_info
        wrapper.cache_clear = lambda: (cache.cache_clear(),
                                      setattr(wrapper, '_cache', {}))
        return wrapper
    return decorator

from rtree import index
from collections import namedtuple

GameObject = namedtuple('GameObject', ['id', 'x', 'y', 'width', 'height', 'type'])

class SpatialIndex:
    def __init__(self):
        # Properties for R-tree optimization
        p = index.Property()
        p.dimension = 2
        p.buffering_capacity = 10
        p.fill_factor = 0.7

        self.idx = index.Index(properties=p)
        self.objects = {}  # id -> GameObject

    def insert(self, game_object: GameObject):
        bbox = (
            game_object.x,
            game_object.y,
            game_object.x + game_object.width,
            game_object.y + game_object.height
        )
        self.idx.insert(game_object.id, bbox)
        self.objects[game_object.id] = game_object

    def find_collisions(self, x, y, width, height):
        """Find all objects that intersect with given rectangle"""
        bbox = (x, y, x + width, y + height)
        collision_ids = list(self.idx.intersection(bbox))
        return [self.objects[obj_id] for obj_id in collision_ids]

    def find_nearby(self, x, y, radius):
        """Find objects within radius"""
        bbox = (x - radius, y - radius, x + radius, y + radius)
        nearby_ids = list(self.idx.intersection(bbox))

        # Filter by actual distance for circular search
        nearby_objects = []
        for obj_id in nearby_ids:
            obj = self.objects[obj_id]
            obj_center_x = obj.x + obj.width / 2
            obj_center_y = obj.y + obj.height / 2
            distance = ((x - obj_center_x) ** 2 + (y - obj_center_y) ** 2) ** 0.5

            if distance <= radius:
                nearby_objects.append(obj)

        return nearby_objects

from sortedcontainers import SortedDict, SortedList
from collections import defaultdict
from dataclasses import dataclass
from typing import Dict, List

@dataclass
class Item:
    id: str
    name: str
    rarity: int  # 1-5, higher is rarer
    value: int
    weight: float
    stackable: bool
    max_stack: int = 1

class GameInventory:
    def __init__(self, max_weight: float = 100.0):
        self.max_weight = max_weight
        self.current_weight = 0.0

        # Multiple indexes for different access patterns
        self.items_by_rarity = SortedDict()  # rarity -> SortedList of items
        self.items_by_value = SortedList(key=lambda x: -x.value)  # Highest value first
        self.stacks = defaultdict(int)  # item_id -> quantity
        self.item_lookup = {}  # item_id -> Item

    def add_item(self, item: Item, quantity: int = 1) -> bool:
        """Add item to inventory if weight allows"""
        total_weight = item.weight * quantity
        if self.current_weight + total_weight > self.max_weight:
            return False

        # Handle stacking
        if item.stackable and item.id in self.stacks:
            current_stack = self.stacks[item.id]
            if current_stack + quantity <= item.max_stack:
                self.stacks[item.id] += quantity
                self.current_weight += total_weight
                return True
            else:
                # Partial add up to max stack
                can_add = item.max_stack - current_stack
                if can_add > 0:
                    self.stacks[item.id] = item.max_stack
                    self.current_weight += item.weight * can_add
                return can_add > 0

        # Add as new stack
        self.stacks[item.id] = quantity
        self.item_lookup[item.id] = item
        self.current_weight += total_weight

        # Update indexes
        if item.rarity not in self.items_by_rarity:
            self.items_by_rarity[item.rarity] = SortedList(key=lambda x: x.name)

        self.items_by_rarity[item.rarity].add(item)
        self.items_by_value.add(item)

        return True

    def get_most_valuable_items(self, count: int = 10) -> List[Item]:
        """Get top N most valuable items"""
        return list(self.items_by_value[:count])

    def get_items_by_rarity(self, min_rarity: int) -> List[Item]:
        """Get all items of minimum rarity or higher"""
        items = []
        for rarity in range(min_rarity, 6):  # 1-5 rarity scale
            if rarity in self.items_by_rarity:
                items.extend(self.items_by_rarity[rarity])
        return items

import heapq
from collections import defaultdict, deque
from dataclasses import dataclass, field
from typing import Set, List, Tuple, Optional

@dataclass(order=True)
class PathNode:
    f_cost: float  # Total cost (g + h)
    g_cost: float = field(compare=False)  # Distance from start
    h_cost: float = field(compare=False)  # Heuristic to goal
    position: Tuple[int, int] = field(compare=False)
    parent: Optional['PathNode'] = field(compare=False, default=None)

class AStar:
    def __init__(self, grid_width: int, grid_height: int):
        self.width = grid_width
        self.height = grid_height
        self.obstacles: Set[Tuple[int, int]] = set()

    def add_obstacle(self, x: int, y: int):
        self.obstacles.add((x, y))

    def heuristic(self, pos1: Tuple[int, int], pos2: Tuple[int, int]) -> float:
        """Manhattan distance heuristic"""
        return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

    def get_neighbors(self, pos: Tuple[int, int]) -> List[Tuple[int, int]]:
        """Get valid neighboring positions"""
        x, y = pos
        neighbors = []

        for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:  # 4-directional
            nx, ny = x + dx, y + dy

            if (0 <= nx < self.width and
                0 <= ny < self.height and
                (nx, ny) not in self.obstacles):
                neighbors.append((nx, ny))

        return neighbors

    def find_path(self, start: Tuple[int, int], goal: Tuple[int, int]) -> Optional[List[Tuple[int, int]]]:
        """Find shortest path using A* algorithm"""
        open_heap = []
        open_set = {}  # position -> node for O(1) lookup
        closed_set = set()

        start_node = PathNode(
            f_cost=0,
            g_cost=0,
            h_cost=self.heuristic(start, goal),
            position=start
        )
        start_node.f_cost = start_node.g_cost + start_node.h_cost

        heapq.heappush(open_heap, start_node)
        open_set[start] = start_node

        while open_heap:
            current = heapq.heappop(open_heap)

            if current.position in closed_set:
                continue

            closed_set.add(current.position)

            if current.position == goal:
                # Reconstruct path
                path = []
                node = current
                while node:
                    path.append(node.position)
                    node = node.parent
                return path[::-1]  # Reverse to get start->goal

            for neighbor_pos in self.get_neighbors(current.position):
                if neighbor_pos in closed_set:
                    continue

                tentative_g = current.g_cost + 1  # Uniform cost

                if neighbor_pos in open_set:
                    neighbor = open_set[neighbor_pos]
                    if tentative_g < neighbor.g_cost:
                        neighbor.g_cost = tentative_g
                        neighbor.f_cost = neighbor.g_cost + neighbor.h_cost
                        neighbor.parent = current
                        heapq.heappush(open_heap, neighbor)
                else:
                    neighbor = PathNode(
                        f_cost=0,
                        g_cost=tentative_g,
                        h_cost=self.heuristic(neighbor_pos, goal),
                        position=neighbor_pos,
                        parent=current
                    )
                    neighbor.f_cost = neighbor.g_cost + neighbor.h_cost

                    heapq.heappush(open_heap, neighbor)
                    open_set[neighbor_pos] = neighbor

        return None  # No path found

from sortedcontainers import SortedDict
from collections import defaultdict, deque
from dataclasses import dataclass
from decimal import Decimal
import time
from typing import Dict, List, Optional

@dataclass
class Order:
    order_id: str
    price: Decimal
    quantity: int
    side: str  # 'buy' or 'sell'
    timestamp: float
    trader_id: str

class OrderBook:
    def __init__(self, symbol: str):
        self.symbol = symbol

        # Buy orders: highest price first (reverse=True)
        self.bids = SortedDict(lambda: deque())

        # Sell orders: lowest price first
        self.asks = SortedDict(lambda: deque())

        # Fast order lookup
        self.orders: Dict[str, Order] = {}

        # Price level tracking
        self.bid_prices = SortedDict()  # price -> total_quantity
        self.ask_prices = SortedDict()  # price -> total_quantity

    def add_order(self, order: Order) -> List[Dict]:
        """Add order and return any trades executed"""
        trades = []
        remaining_quantity = order.quantity

        if order.side == 'buy':
            # Check for immediate execution against asks
            while remaining_quantity > 0 and self.asks:
                best_ask_price = self.asks.peekitem(0)[0]  # Lowest ask

                if order.price >= best_ask_price:
                    # Execute trade
                    ask_queue = self.asks[best_ask_price]
                    ask_order = ask_queue[0]

                    trade_quantity = min(remaining_quantity, ask_order.quantity)
                    trade = {
                        'price': best_ask_price,
                        'quantity': trade_quantity,
                        'buy_order_id': order.order_id,
                        'sell_order_id': ask_order.order_id,
                        'timestamp': time.time()
                    }
                    trades.append(trade)

                    # Update quantities
                    remaining_quantity -= trade_quantity
                    ask_order.quantity -= trade_quantity

                    # Remove filled order
                    if ask_order.quantity == 0:
                        ask_queue.popleft()
                        del self.orders[ask_order.order_id]

                        if not ask_queue:
                            del self.asks[best_ask_price]
                            del self.ask_prices[best_ask_price]
                        else:
                            self.ask_prices[best_ask_price] -= trade_quantity
                else:
                    break

            # Add remaining quantity to bid book
            if remaining_quantity > 0:
                order.quantity = remaining_quantity
                self._add_to_book(order, self.bids, self.bid_prices)

        else:  # sell order
            # Check for immediate execution against bids
            while remaining_quantity > 0 and self.bids:
                best_bid_price = self.bids.peekitem(-1)[0]  # Highest bid

                if order.price <= best_bid_price:
                    # Execute trade
                    bid_queue = self.bids[best_bid_price]
                    bid_order = bid_queue[0]

                    trade_quantity = min(remaining_quantity, bid_order.quantity)
                    trade = {
                        'price': best_bid_price,
                        'quantity': trade_quantity,
                        'buy_order_id': bid_order.order_id,
                        'sell_order_id': order.order_id,
                        'timestamp': time.time()
                    }
                    trades.append(trade)

                    # Update quantities
                    remaining_quantity -= trade_quantity
                    bid_order.quantity -= trade_quantity

                    # Remove filled order
                    if bid_order.quantity == 0:
                        bid_queue.popleft()
                        del self.orders[bid_order.order_id]

                        if not bid_queue:
                            del self.bids[best_bid_price]
                            del self.bid_prices[best_bid_price]
                        else:
                            self.bid_prices[best_bid_price] -= trade_quantity
                else:
                    break

            # Add remaining quantity to ask book
            if remaining_quantity > 0:
                order.quantity = remaining_quantity
                self._add_to_book(order, self.asks, self.ask_prices)

        return trades

    def _add_to_book(self, order: Order, price_levels: SortedDict, price_tracking: SortedDict):
        """Add order to appropriate price level"""
        if order.price not in price_levels:
            price_levels[order.price] = deque()
            price_tracking[order.price] = 0

        price_levels[order.price].append(order)
        price_tracking[order.price] += order.quantity
        self.orders[order.order_id] = order

    def get_best_bid(self) -> Optional[Decimal]:
        """Get highest bid price"""
        return self.bids.peekitem(-1)[0] if self.bids else None

    def get_best_ask(self) -> Optional[Decimal]:
        """Get lowest ask price"""
        return self.asks.peekitem(0)[0] if self.asks else None

    def get_spread(self) -> Optional[Decimal]:
        """Get bid-ask spread"""
        best_bid = self.get_best_bid()
        best_ask = self.get_best_ask()

        if best_bid and best_ask:
            return best_ask - best_bid
        return None

    def get_market_depth(self, levels: int = 5) -> Dict:
        """Get order book depth"""
        bids = []
        asks = []

        # Get top bid levels
        for i, (price, queue) in enumerate(reversed(self.bids.items())):
            if i >= levels:
                break
            quantity = self.bid_prices[price]
            bids.append({'price': price, 'quantity': quantity})

        # Get top ask levels
        for i, (price, queue) in enumerate(self.asks.items()):
            if i >= levels:
                break
            quantity = self.ask_prices[price]
            asks.append({'price': price, 'quantity': quantity})

        return {'bids': bids, 'asks': asks}

# Thread-safe by design
safe_collections = {
    'queue.Queue': 'Built-in thread safety',
    'collections.deque': 'Atomic append/popleft operations',
    'multiprocessing.Manager': 'Process-safe alternatives',
}

# Require external synchronization
unsafe_collections = {
    'dict, list, set': 'Use threading.Lock',
    'sortedcontainers': 'Use threading.RLock',
    'pyrsistent': 'Immutable = thread-safe reads',
}

from threading import RLock
from concurrent.futures import ThreadPoolExecutor
import asyncio

class ThreadSafeCollectionWrapper:
    """Generic thread-safe wrapper for any collection"""
    def __init__(self, collection_class, *args, **kwargs):
        self._collection = collection_class(*args, **kwargs)
        self._lock = RLock()

    def __getattr__(self, name):
        def wrapper(*args, **kwargs):
            with self._lock:
                return getattr(self._collection, name)(*args, **kwargs)
        return wrapper

# Usage examples
thread_safe_sorted_list = ThreadSafeCollectionWrapper(
    sortedcontainers.SortedList
)

# For high-concurrency scenarios
class LockFreeQueue:
    """Lock-free queue using atomic operations"""
    def __init__(self):
        self._queue = collections.deque()

    def put(self, item):
        # Atomic operation
        self._queue.append(item)

    def get(self):
        try:
            # Atomic operation
            return self._queue.popleft()
        except IndexError:
            return None

# Migration assessment framework
migration_checklist = {
    'performance_bottlenecks': [
        'Profile current performance',
        'Identify hotspots in collection operations',
        'Measure memory usage patterns'
    ],
    'api_compatibility': [
        'Audit current collection usage',
        'Identify breaking changes needed',
        'Plan backwards compatibility layer'
    ],
    'testing_strategy': [
        'Create performance benchmarks',
        'Design correctness tests',
        'Plan rollback procedures'
    ]
}

# Example: Migrating from dict to SortedDict
from sortedcontainers import SortedDict

class BackwardsCompatibleSortedDict:
    """Migration wrapper maintaining dict interface"""
    def __init__(self, initial_data=None):
        self._sorted_dict = SortedDict(initial_data or {})
        self._migration_mode = True  # Flag for logging

    def __getitem__(self, key):
        if self._migration_mode:
            self._log_access('get', key)
        return self._sorted_dict[key]

    def __setitem__(self, key, value):
        if self._migration_mode:
            self._log_access('set', key)
        self._sorted_dict[key] = value

    def keys(self):
        # Returns sorted keys (new behavior)
        return self._sorted_dict.keys()

    def items(self):
        # Returns sorted items (new behavior)
        return self._sorted_dict.items()

    def _log_access(self, operation, key):
        # Log for migration monitoring
        print(f"Migration: {operation} access to key {key}")

    def disable_migration_mode(self):
        self._migration_mode = False

from sortedcontainers import SortedDict, SortedList
from collections import defaultdict

class MultiIndexCollection:
    """Maintain multiple indexes for different access patterns"""
    def __init__(self):
        # Primary storage
        self.data = {}  # id -> object

        # Multiple indexes
        self.by_timestamp = SortedList(key=lambda x: x.timestamp)
        self.by_priority = SortedDict()  # priority -> list of objects
        self.by_category = defaultdict(list)  # category -> list of objects

        # Tag-based indexing
        self.tags = defaultdict(set)  # tag -> set of object ids

    def add(self, obj):
        """Add object with automatic indexing"""
        self.data[obj.id] = obj

        # Update all indexes
        self.by_timestamp.add(obj)

        if obj.priority not in self.by_priority:
            self.by_priority[obj.priority] = []
        self.by_priority[obj.priority].append(obj)

        self.by_category[obj.category].append(obj)

        # Index tags
        for tag in getattr(obj, 'tags', []):
            self.tags[tag].add(obj.id)

    def find_by_time_range(self, start_time, end_time):
        """O(log n) time range query"""
        # Binary search for range
        start_idx = self.by_timestamp.bisect_left(type('', (), {'timestamp': start_time})())
        end_idx = self.by_timestamp.bisect_right(type('', (), {'timestamp': end_time})())

        return list(self.by_timestamp[start_idx:end_idx])

    def find_by_priority(self, min_priority):
        """Get all objects with priority >= min_priority"""
        results = []
        for priority in self.by_priority.irange(min_priority, None):
            results.extend(self.by_priority[priority])
        return results

    def find_by_tags(self, required_tags):
        """Find objects having all required tags"""
        if not required_tags:
            return []

        # Intersection of all tag sets
        result_ids = self.tags[required_tags[0]]
        for tag in required_tags[1:]:
            result_ids = result_ids.intersection(self.tags[tag])

        return [self.data[obj_id] for obj_id in result_ids]

import numpy as np
from array import array
import mmap
import os

class MemoryOptimizedCollection:
    """Techniques for handling large-scale data efficiently"""

    def __init__(self, data_type='int32'):
        self.data_type = data_type
        self.memory_mapped_file = None
        self.compressed_data = None

    def use_array_instead_of_list(self, data):
        """Use array.array for homogeneous numeric data"""
        # Memory savings: 4x for integers, 2x for floats
        if self.data_type == 'int32':
            return array('i', data)  # 'i' = signed int (4 bytes)
        elif self.data_type == 'float64':
            return array('d', data)  # 'd' = double (8 bytes)
        else:
            return list(data)

    def use_memory_mapping(self, filename, data_size):
        """Memory-map large datasets"""
        # Create memory-mapped array
        if not os.path.exists(filename):
            # Create file with zeros
            np.memmap(filename, dtype=self.data_type, mode='w+', shape=(data_size,))

        # Map existing file
        self.memory_mapped_file = np.memmap(
            filename,
            dtype=self.data_type,
            mode='r+'
        )
        return self.memory_mapped_file

    def use_compression(self, data):
        """Compress data for storage"""
        import gzip
        import pickle

        compressed = gzip.compress(pickle.dumps(data))
        return compressed

    def estimate_memory_usage(self, collection_type, num_items, item_size_bytes):
        """Estimate memory usage for different collection types"""
        estimates = {
            'list': num_items * (item_size_bytes + 8),  # 8 bytes pointer overhead
            'dict': num_items * (item_size_bytes + 24),  # Hash table overhead
            'set': num_items * (item_size_bytes + 16),   # Set overhead
            'sortedlist': num_items * (item_size_bytes + 8),  # Similar to list
            'array': num_items * item_size_bytes,        # No pointer overhead
        }

        return estimates.get(collection_type, estimates['list'])

# Example usage for different scenarios
class ScenarioOptimizer:
    @staticmethod
    def optimize_for_financial_data():
        """Optimize for high-frequency financial data"""
        # Use numpy arrays for numerical data
        prices = np.array([], dtype=np.float64)
        timestamps = np.array([], dtype=np.int64)

        # Use memory mapping for historical data
        historical_data = np.memmap(
            'historical_prices.dat',
            dtype=np.float64,
            mode='r'
        )

        return prices, timestamps, historical_data

    @staticmethod
    def optimize_for_web_sessions():
        """Optimize for web session management"""
        from collections import OrderedDict

        # LRU cache with size limits
        active_sessions = OrderedDict()

        # Use weak references for temporary data
        import weakref
        temporary_data = weakref.WeakValueDictionary()

        return active_sessions, temporary_data

    @staticmethod
    def optimize_for_scientific_computing():
        """Optimize for scientific workloads"""
        import scipy.sparse

        # Sparse matrices for large datasets with few non-zero values
        sparse_matrix = scipy.sparse.csr_matrix((1000000, 1000000))

        # Structured arrays for heterogeneous data
        structured_data = np.array([
            (1, 2.5, 'item1'),
            (2, 3.7, 'item2')
        ], dtype=[('id', 'i4'), ('value', 'f8'), ('name', 'U10')])

        return sparse_matrix, structured_data

# Phase 1: Built-in collections for speed
user_profiles = {}  # user_id -> profile_dict
user_posts = defaultdict(list)  # user_id -> list of posts
post_likes = defaultdict(set)  # post_id -> set of user_ids
timeline_cache = {}  # user_id -> cached timeline

# Phase 2: Strategic upgrades
from sortedcontainers import SortedList

class StartupCollections:
    def __init__(self):
        # Keep simple collections where appropriate
        self.users = {}
        self.posts = {}

        # Upgrade specific hotspots
        self.trending_posts = SortedList(key=lambda x: -x.engagement_score)
        self.user_activity = SortedList(key=lambda x: x.last_active)

        # Simple caching for performance
        self.cache = {}
        self.cache_ttl = 300  # 5 minutes

    def get_trending_posts(self, limit=20):
        return list(self.trending_posts[:limit])

    def get_recent_users(self, limit=100):
        return list(self.user_activity[-limit:])

import numpy as np
from sortedcontainers import SortedDict
from collections import deque
import time

class EnterpriseFinancialCollections:
    def __init__(self):
        # Pre-allocated arrays for performance
        self.price_buffer = np.zeros(1000000, dtype=np.float64)
        self.timestamp_buffer = np.zeros(1000000, dtype=np.int64)
        self.buffer_index = 0

        # Lock-free collections for concurrency
        self.order_queues = {
            'buy': deque(),
            'sell': deque()
        }

        # Sorted structures for order books
        self.bid_prices = SortedDict()
        self.ask_prices = SortedDict()

        # Risk calculation caches
        self.position_cache = {}
        self.risk_cache = {}
        self.cache_timestamps = {}

        # Performance monitoring
        self.operation_times = deque(maxlen=10000)

    def add_market_data(self, price, timestamp):
        """Ultra-fast market data ingestion"""
        start_time = time.perf_counter()

        # Use pre-allocated buffers
        idx = self.buffer_index % len(self.price_buffer)
        self.price_buffer[idx] = price
        self.timestamp_buffer[idx] = timestamp
        self.buffer_index += 1

        # Update risk calculations if needed
        self._update_risk_if_needed()

        # Track performance
        operation_time = time.perf_counter() - start_time
        self.operation_times.append(operation_time)

    def _update_risk_if_needed(self):
        """Lazy risk calculation with caching"""
        current_time = time.time()
        if current_time - self.cache_timestamps.get('risk', 0) > 0.001:  # 1ms cache
            # Perform risk calculations
            self._calculate_risk()
            self.cache_timestamps['risk'] = current_time

    def get_performance_stats(self):
        """Monitor collection performance"""
        if not self.operation_times:
            return {}

        times = list(self.operation_times)
        return {
            'avg_latency_us': np.mean(times) * 1_000_000,
            'p99_latency_us': np.percentile(times, 99) * 1_000_000,
            'operations_per_second': len(times) / (max(times) - min(times)) if len(times) > 1 else 0
        }

import polars as pl
import numpy as np
from pathlib import Path

class DataScienceCollections:
    def __init__(self, data_path: Path):
        self.data_path = data_path

        # Use Polars for large-scale data processing
        self.df = None
        self.lazy_df = None

        # Feature engineering cache
        self.feature_cache = {}

        # Memory-mapped arrays for embeddings
        self.embeddings = None

    def load_data_efficiently(self, chunk_size=1000000):
        """Load large datasets with memory efficiency"""
        # Use lazy evaluation
        self.lazy_df = pl.scan_parquet(str(self.data_path / "*.parquet"))

        # Streaming processing for data that doesn't fit in memory
        return self.lazy_df

    def feature_engineering_pipeline(self):
        """Memory-efficient feature engineering"""
        processed = (
            self.lazy_df
            .with_columns([
                # Efficient string operations
                pl.col("text_column").str.len_chars().alias("text_length"),

                # Categorical encoding
                pl.col("category").cast(pl.Categorical).alias("category_encoded"),

                # Date features
                pl.col("timestamp").dt.date().alias("date"),
                pl.col("timestamp").dt.hour().alias("hour"),
            ])
            .filter(pl.col("text_length") > 10)  # Filter early
            .group_by("category_encoded")
            .agg([
                pl.col("numerical_column").mean().alias("category_mean"),
                pl.col("numerical_column").std().alias("category_std")
            ])
        )

        # Collect only when needed
        return processed.collect()

    def setup_embeddings_storage(self, vocab_size, embedding_dim):
        """Memory-mapped storage for large embedding matrices"""
        embedding_file = self.data_path / "embeddings.dat"

        # Create memory-mapped embedding matrix
        self.embeddings = np.memmap(
            embedding_file,
            dtype=np.float32,
            mode='w+',
            shape=(vocab_size, embedding_dim)
        )

        return self.embeddings

    def batch_processing_generator(self, batch_size=10000):
        """Generator for batch processing large datasets"""
        for batch in self.lazy_df.iter_slices(batch_size):
            # Process each batch
            yield batch.collect()

import time
import memory_profiler
import psutil
from contextlib import contextmanager
from typing import Dict, List, Any, Callable
import gc

class CollectionBenchmark:
    def __init__(self):
        self.results = {}
        self.baseline_memory = None

    @contextmanager
    def measure_performance(self, operation_name: str):
        """Context manager for measuring performance"""
        # Force garbage collection
        gc.collect()

        # Measure initial state
        start_time = time.perf_counter()
        start_memory = psutil.Process().memory_info().rss

        try:
            yield
        finally:
            # Measure final state
            end_time = time.perf_counter()
            end_memory = psutil.Process().memory_info().rss

            # Store results
            self.results[operation_name] = {
                'execution_time': end_time - start_time,
                'memory_delta': end_memory - start_memory,
                'timestamp': time.time()
            }

    def benchmark_collection_operations(self, collection_class, data_size=100000):
        """Comprehensive benchmark for any collection type"""
        results = {}

        # Test data
        test_data = list(range(data_size))

        # Initialization benchmark
        with self.measure_performance(f"{collection_class.__name__}_init"):
            collection = collection_class()

        # Insertion benchmark
        with self.measure_performance(f"{collection_class.__name__}_insert"):
            for item in test_data:
                if hasattr(collection, 'add'):
                    collection.add(item)
                elif hasattr(collection, 'append'):
                    collection.append(item)
                else:
                    collection[item] = item

        # Lookup benchmark
        if hasattr(collection, '__contains__') or hasattr(collection, '__getitem__'):
            with self.measure_performance(f"{collection_class.__name__}_lookup"):
                for i in range(0, data_size, 100):  # Sample lookups
                    if hasattr(collection, '__contains__'):
                        _ = i in collection
                    else:
                        try:
                            _ = collection[i]
                        except (KeyError, IndexError):
                            pass

        return self.results

# Example usage
def compare_sorted_collections():
    """Compare different sorted collection implementations"""
    from sortedcontainers import SortedList
    import bisect

    benchmark = CollectionBenchmark()
    data_sizes = [1000, 10000, 100000]

    results = {}

    for size in data_sizes:
        print(f"Testing with {size} elements...")

        # Test built-in list with bisect
        class BisectList:
            def __init__(self):
                self.data = []

            def add(self, item):
                bisect.insort(self.data, item)

            def __contains__(self, item):
                idx = bisect.bisect_left(self.data, item)
                return idx < len(self.data) and self.data[idx] == item

        # Benchmark SortedList
        sorted_results = benchmark.benchmark_collection_operations(
            SortedList, size
        )

        # Benchmark bisect-based approach
        bisect_results = benchmark.benchmark_collection_operations(
            BisectList, size
        )

        results[size] = {
            'sortedcontainers': sorted_results,
            'bisect_list': bisect_results
        }

    return results

def memory_profiling_example():
    """Example of memory profiling for collection choice"""
    @memory_profiler.profile
    def test_collection_memory(collection_class, size=100000):
        collection = collection_class()

        # Fill collection
        for i in range(size):
            if hasattr(collection, 'add'):
                collection.add(i)
            else:
                collection.append(i)

        return collection

    # Test different collections
    import array
    from sortedcontainers import SortedList

    print("Memory usage for list:")
    list_collection = test_collection_memory(list)

    print("Memory usage for array:")
    array_collection = test_collection_memory(lambda: array.array('i'))

    print("Memory usage for SortedList:")
    sorted_collection = test_collection_memory(SortedList)

import unittest
import random
from typing import Any, Set, List
from abc import ABC, abstractmethod

class CollectionTestSuite(ABC):
    """Abstract base class for testing collection implementations"""

    @abstractmethod
    def create_collection(self) -> Any:
        """Create an instance of the collection to test"""
        pass

    @abstractmethod
    def add_item(self, collection: Any, item: Any) -> None:
        """Add an item to the collection"""
        pass

    @abstractmethod
    def contains_item(self, collection: Any, item: Any) -> bool:
        """Check if collection contains item"""
        pass

class SortedCollectionTest(CollectionTestSuite, unittest.TestCase):
    """Test suite for sorted collections"""

    def create_collection(self):
        from sortedcontainers import SortedList
        return SortedList()

    def add_item(self, collection, item):
        collection.add(item)

    def contains_item(self, collection, item):
        return item in collection

    def test_maintains_sorted_order(self):
        """Test that collection maintains sorted order"""
        collection = self.create_collection()
        test_data = [5, 2, 8, 1, 9, 3]

        for item in test_data:
            self.add_item(collection, item)

        # Verify sorted order
        for i in range(len(collection) - 1):
            self.assertLessEqual(collection[i], collection[i + 1])

    def test_random_operations(self):
        """Stress test with random operations"""
        collection = self.create_collection()
        reference_set = set()

        for _ in range(1000):
            operation = random.choice(['add', 'remove', 'contains'])
            value = random.randint(1, 100)

            if operation == 'add':
                self.add_item(collection, value)
                reference_set.add(value)

            elif operation == 'remove' and value in reference_set:
                collection.remove(value)
                reference_set.remove(value)

            elif operation == 'contains':
                collection_result = self.contains_item(collection, value)
                reference_result = value in reference_set
                self.assertEqual(collection_result, reference_result)

        # Final consistency check
        self.assertEqual(set(collection), reference_set)

class ConcurrencyTest(unittest.TestCase):
    """Test collection behavior under concurrent access"""

    def test_thread_safety(self):
        """Test thread safety of collections"""
        import threading
        from queue import Queue

        shared_queue = Queue()
        results = []

        def producer(queue, start, end):
            for i in range(start, end):
                queue.put(i)

        def consumer(queue, results_list):
            while True:
                try:
                    item = queue.get(timeout=1)
                    results_list.append(item)
                    queue.task_done()
                except:
                    break

        # Start threads
        threads = []

        # Producer threads
        for i in range(0, 1000, 100):
            t = threading.Thread(target=producer, args=(shared_queue, i, i + 100))
            t.start()
            threads.append(t)

        # Consumer thread
        consumer_thread = threading.Thread(target=consumer, args=(shared_queue, results))
        consumer_thread.start()
        threads.append(consumer_thread)

        # Wait for producers
        for t in threads[:-1]:  # All except consumer
            t.join()

        # Wait for queue to be empty
        shared_queue.join()

        # Verify all items were processed
        self.assertEqual(len(set(results)), 1000)

def property_based_testing_example():
    """Example using hypothesis for property-based testing"""
    try:
        from hypothesis import given, strategies as st

        @given(st.lists(st.integers()))
        def test_sorted_property(data):
            from sortedcontainers import SortedList

            sorted_list = SortedList()
            for item in data:
                sorted_list.add(item)

            # Property: list should be sorted
            for i in range(len(sorted_list) - 1):
                assert sorted_list[i] <= sorted_list[i + 1]

            # Property: should contain all original items
            assert set(sorted_list) == set(data)

        # Run the test
        test_sorted_property()
        print("Property-based testing passed!")

    except ImportError:
        print("hypothesis not available for property-based testing")

# WRONG: Using list for frequent membership tests
large_list = list(range(1000000))

def slow_membership_test(item):
    return item in large_list  # O(n) operation!

# CORRECT: Use set for membership tests
large_set = set(range(1000000))

def fast_membership_test(item):
    return item in large_set  # O(1) operation

# WRONG: Sorting after every insertion
items = []
def add_item_wrong(item):
    items.append(item)
    items.sort()  # O(n log n) every time!

# CORRECT: Use SortedList for maintained order
from sortedcontainers import SortedList
sorted_items = SortedList()

def add_item_correct(item):
    sorted_items.add(item)  # O(log n) insertion

# WRONG: Using dict for homogeneous numerical data
coordinates = {}
for i in range(1000000):
    coordinates[i] = {'x': i * 1.5, 'y': i * 2.0}

# CORRECT: Use numpy arrays
import numpy as np
coordinates = np.zeros((1000000, 2), dtype=np.float64)
coordinates[:, 0] = np.arange(1000000) * 1.5  # x coordinates
coordinates[:, 1] = np.arange(1000000) * 2.0  # y coordinates

# WRONG: Assuming collections are thread-safe
shared_dict = {}

def unsafe_update(key, value):
    if key not in shared_dict:  # Race condition here!
        shared_dict[key] = []
    shared_dict[key].append(value)

# CORRECT: Use proper synchronization
import threading
from collections import defaultdict

shared_dict_safe = defaultdict(list)
dict_lock = threading.RLock()

def safe_update(key, value):
    with dict_lock:
        shared_dict_safe[key].append(value)

# WRONG: Coarse-grained locking
import threading

class SlowSharedCollection:
    def __init__(self):
        self.data = {}
        self.lock = threading.RLock()

    def get(self, key):
        with self.lock:  # Locks entire collection
            return self.data.get(key)

    def set(self, key, value):
        with self.lock:  # Locks entire collection
            self.data[key] = value

# CORRECT: Fine-grained locking or lock-free structures
from collections import defaultdict
import threading

class FastSharedCollection:
    def __init__(self):
        self.data = {}
        self.locks = defaultdict(threading.RLock)  # Per-key locks

    def get(self, key):
        # Read operations often don't need locks for simple values
        return self.data.get(key)

    def set(self, key, value):
        with self.locks[key]:  # Lock only specific key
            self.data[key] = value

# WRONG: Creating cycles that prevent garbage collection
class Node:
    def __init__(self, value):
        self.value = value
        self.parent = None
        self.children = []

    def add_child(self, child):
        child.parent = self  # Creates cycle!
        self.children.append(child)

# CORRECT: Use weak references
import weakref

class NodeSafe:
    def __init__(self, value):
        self.value = value
        self._parent = None
        self.children = []

    @property
    def parent(self):
        return self._parent() if self._parent else None

    @parent.setter
    def parent(self, value):
        self._parent = weakref.ref(value) if value else None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

# WRONG: String concatenation in loops
result = ""
for item in large_list:
    result += str(item) + ","  # Creates new string each time!

# CORRECT: Use join or io.StringIO
result = ",".join(str(item) for item in large_list)

# Or for complex building:
import io
buffer = io.StringIO()
for item in large_list:
    buffer.write(str(item))
    buffer.write(",")
result = buffer.getvalue()

# Future-safe collection design patterns
from typing import Protocol, TypeVar, Generic
from abc import ABC, abstractmethod

T = TypeVar('T')

class SortedCollection(Protocol[T]):
    """Protocol for sorted collections - future-safe interface"""
    def add(self, item: T) -> None: ...
    def remove(self, item: T) -> None: ...
    def __contains__(self, item: T) -> bool: ...
    def __iter__(self) -> Iterator[T]: ...
    def __len__(self) -> int: ...

class FutureSafeWrapper(Generic[T]):
    """Wrapper that can adapt to new implementations"""
    def __init__(self, implementation: SortedCollection[T]):
        self._impl = implementation
        self._version = "1.0"

    def migrate_to_new_implementation(self, new_impl_class):
        """Migrate to newer implementation while preserving data"""
        old_data = list(self._impl)
        self._impl = new_impl_class()

        for item in old_data:
            self._impl.add(item)

        self._version = "2.0"

    def __getattr__(self, name):
        return getattr(self._impl, name)

# Current GIL-protected patterns (will become bottlenecks)
shared_dict = {}  # GIL provides implicit synchronization

# Future requirement: Explicit concurrent-safe collections
from concurrent.futures import ThreadPoolExecutor
import pyrsistent

# Immutable collections become strategically advantageous
shared_state = pyrsistent.m(counter=0, data=[])

def update_shared_state(new_data):
    # Atomic updates without locks through immutability
    return shared_state.transform(['data'], lambda x: x.append(new_data))