dictionary के Cartesian product के लिए एक-पास और रिकर्सिव Python तरीके

Python में dictionary का Cartesian product बनाने के व्यावहारिक तरीके: दो-पास बेसलाइन, itertools के साथ एक-पास, और रिकर्सिव समाधान; प्रदर्शन तुलना भी शामिल.

किसी dictionary का अपने ही साथ Cartesian product निकालना तब आम पैटर्न है, जब आपको keys के ट्यूपल और उनके अनुरूप मानों पर संख्यात्मक समाकलन चाहिए। यहाँ लक्ष्य repeat लंबाई के सभी key-ट्यूपल गिनना और हर ट्यूपल के लिए मेल खाते Fraction मानों को गुणा करना है। एक सीधा तरीका दो स्वतंत्र products बनाता है—एक keys के लिए और एक values के लिए—और फिर उन्हें index से जोड़ देता है। यह काम तो करता है, लेकिन दो पास लगते हैं और बीच में बनने वाली सूचियाँ अनावश्यक मेमोरी लेती हैं, जिन्हें टाला जा सकता है।

बेसलाइन: दो products—एक keys के लिए और एक values के लिए

नीचे दिया उदाहरण वही पैटर्न दिखाता है जिसमें दो बार लूप चलता है: पहले सभी key-ट्यूपल बनते हैं, फिर सभी value-ट्यूपल, और मानों को गुणा करने के लिए math.prod इस्तेमाल होता है। सब कुछ standard library के भीतर रहता है।

import itertools as tools
import math as m
from fractions import Fraction as F
weights = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}
repeat_count = 2  # परिवर्तनीय; कोई भी शून्य या उससे बड़ा पूर्णांक हो सकता है
key_tuples = list(tools.product(weights, repeat=repeat_count))
value_products = list(map(m.prod, tools.product(weights.values(), repeat=repeat_count)))
result = {key_tuples[i]: value_products[i] for i in range(len(value_products))}
print(result)

यह अपेक्षित मैपिंग बनाता है: key-ट्यूपल से उनके Fraction मानों के गुणनफल तक। कमी यह है कि मेहनत दोगुनी हो जाती है और दो समानांतर सूचियाँ संभालने से अतिरिक्त मेमोरी लगती है।

वास्तव में ज़रूरत क्या है

कुंजियों को ट्यूपल के रूप में निकालना है और मान Fraction का साधारण गुणनफल होना चाहिए। किसी गैर-मानक पैकेज पर निर्भरता नहीं है, और repeat एक परिवर्तनशील मान है; इसलिए निश्चित संख्या वाले घोंसलेदार लूप पर आधारित हल आम नहीं ठहरते। इन सीमाओं के साथ, मूल आवश्यकता है एक ही पास में ऐसे परिणाम निकालना जो एक साथ key-ट्यूपल और उसका गुणित मान दे, या फिर वही मैपिंग इस तरह बनाना कि दो अलग-अलग Cartesian products न बनाने पड़ें।

समाधान 1: itertools के साथ एक-पास dictionary comprehension

दोहरा पास टालने का संक्षिप्त तरीका है कि केवल keys का Cartesian product घुमाएँ और संबंधित मानों का गुणनफल चलते-चलते निकालें। इससे तर्क एक जगह रहता है और दो सूचियों के index-आधारित जोड़ की जरूरत खत्म हो जाती है।

import itertools as tools
import math as m
from fractions import Fraction as F
pool = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}
def cart_dict_onepass(bucket, times=2):
    return {
        keys: m.prod(bucket[k] for k in keys)
        for keys in tools.product(bucket, repeat=times)
    }
print(cart_dict_onepass(pool, times=2))

यह तरीका एक ही comprehension का उपयोग करता है, जो key-ट्यूपल पर चलता है और उनके मानों को math.prod से गुणा करता है। यह पूरी तरह standard library में रहता है और किसी भी repeat मान के साथ स्केल करता है।

समाधान 2: बिना itertools के रिकर्सिव बिल्डर

पूरी तरह itertools से बचना चाहें तो मैपिंग को रिकर्सिव ढंग से बना सकते हैं। क्रिया के न्यूट्रल एलिमेंट से शुरू करें—खाली ट्यूपल जिसे 1 के साथ जोड़ा गया हो—और हर बार एक आयाम जोड़कर क्रॉस-मल्टिप्लाई करें। मूलतः यह “क्रॉस-प्रोडक्ट का क्रॉस-प्रोडक्ट” है, जिसे repeat बार लागू किया जाता है।

from fractions import Fraction as F
pool = {
    'P1': F(7, 120), 'P2': F(20, 120), 'P3': F(6, 120),
    'P4': F(10, 120), 'P6': F(7, 120), 'P6': F(18, 120),
    'P7': F(16, 120), 'P8': F(19, 120), 'P9': F(17, 120)
}
def unfold(state, times=2):
    if times == 0:
        return state
    return unfold(
        {
            prefix + (k2,): state[prefix] * pool[k2]
            for prefix in state for k2 in pool
        },
        times - 1,
    )
def build_map(times=2):
    return unfold({(): 1}, times)
# अगर times के > 0 होने की गारंटी हो, तो आप एक स्तर छोड़ सकते हैं
# और बीज के रूप में एक आयाम पहले से विस्तारित देकर शुरू कर सकते हैं।
def build_map_nonempty(times=2):
    return unfold({(k,): pool[k] for k in pool}, times - 1)
print(build_map(times=2))

यह itertools वाले संस्करण जैसा ही dictionary देता है, और फायदा यह कि यह बिल्कुल भी itertools पर निर्भर नहीं है। ध्यान देने योग्य है कि Python tail recursion को अनुकूलित नहीं करता; बहुत बड़े repeat मानों पर रिकर्सन सीमा जल्दी ही आ जाएगी—उससे बहुत पहले, जब इतने बड़े Cartesian product का गणनात्मक रूप से व्यावहारिक होना संभव हो।

प्रदर्शन संबंधी टिप्पणियाँ

उदाहरण वाले डेटा पर, repeat बराबर 2 के लिए विशेषीकृत सीधा घोंसलेदार इटरेशन लगभग 121 μs आया। itertools के बिना रिकर्सिव तरीका करीब 136–167 μs के दायरे में चला, जबकि एक-पास itertools comprehension लगभग 398 μs पर थी। दो-पास वाला बेसलाइन, जो key और value products अलग-अलग बनाता है, करीब 346 μs लगा। ये आँकड़े उसी मशीन और इनपुट पर देखे गए और दिखाते हैं कि इस काम के बोझ पर बिना itertools वाला रिकर्सिव तरीका व्यवहार में तेज़ हो सकता है, जबकि repeat ठीक-ठीक 2 होने पर तय दो-लूप रूप सबसे तेज़ रहता है।

आगे के मापों में देखा गया कि repeat दीवार-घड़ी समय को कैसे प्रभावित करता है। Cartesian products के लिए अपेक्षित रूप से, समय repeat के साथ घातीय रूप से बढ़ता है, और विभिन्न repeat मानों पर तरीकों के बीच अनुपात लगभग स्थिर रहे। डिक्शनरी का आकार बढ़ाने पर भी यही तस्वीर मिली: repeat बराबर दो होने पर लागत प्रविष्टियों की संख्या के साथ लगभग वर्गानुपाती बढ़ी, और तरीकों की सापेक्ष क्रमबद्धता नहीं बदली। दूसरे शब्दों में, इस कार्य के लिए एसिम्प्टोटिक व्यवहार O(n^repeat) है, और व्यावहारिक चयन मुख्यतः स्थिर गुणांकों और निर्भरताओं पर निर्भर है, न कि big-O के अंतर पर।

यह जानना क्यों उपयोगी है

Cartesian तेजी से फूले-फैले होते हैं, इसलिए बीच की अलोकेशनों और अनावश्यक पास घटाना मायने रखता है। एक-पास रूपरेखा index के जरिए दो सूचियों को बाँधने से बचाती है और गणना को उन keys तक सीमित रखती है जिन पर आप चल रहे हैं। रिकर्सिव रूपरेखा लाइब्रेरी इटरेशन की जगह एक साधारण state विस्तार कदम लाती है और ऊपर दिखाए गए मापों में सामान्य समाधानों में सबसे अच्छा समय दिया। इन ट्रेड-ऑफ़ को समझना आपको ऐसा तरीका चुनने में मदद करता है जो आपकी बाधाओं के लिए पठनीयता, निर्भरताएँ और गति में संतुलन बिठाए।

सारांश

यदि repeat तय और छोटा है, तो {(k1, k2): pool[k1] * pool[k2] for k1 in pool for k2 in pool} जैसा सीधा डबल comprehension पछाड़ना मुश्किल है। जब repeat परिवर्तनशील हो, तो या तो एक-पास itertools comprehension चुनें जो मानों की गणना चलते-चलते करे, या {(): 1} से बीजित बिना itertools वाला रिकर्सिव विस्तार। दोनों standard library में रहते हैं, दोनों key-ट्यूपल से Fraction products की वही मैपिंग बनाते हैं, और दोनों अलग-अलग key और value products बनाने वाले अतिरिक्त पास और मेमोरी ओवरहेड से बचाते हैं। शैलीगत रूप से, स्पष्ट import नामों को बहुत छोटे उपनामों पर तरजीह दें—जब तक कि उपनाम व्यापक रूप से पहचाना न जाता हो; दबाव में कोड पर लौटते समय स्पष्टता काम आती है।