ডিপসেট

ডেপসেট হল একটি বিশেষায়িত ডেটা স্ট্রাকচার যা একটি লক্ষ্যের ট্রানজিটিভ নির্ভরতা জুড়ে দক্ষতার সাথে ডেটা সংগ্রহ করার জন্য। এগুলি নিয়ম প্রক্রিয়াকরণের একটি অপরিহার্য উপাদান।

ডিপসেটের সংজ্ঞায়িত বৈশিষ্ট্য হল এর সময়- এবং স্থান-দক্ষ ইউনিয়ন অপারেশন। ডিপসেট কনস্ট্রাক্টর উপাদানগুলির একটি তালিকা ("সরাসরি") এবং অন্যান্য ডিপসেটের একটি তালিকা ("ট্রানজিটিভ") গ্রহণ করে এবং সমস্ত প্রত্যক্ষ উপাদান এবং সমস্ত ট্রানজিটিভ সেটের মিলন সমন্বিত একটি সেট উপস্থাপন করে একটি ডিপসেট প্রদান করে। ধারণাগতভাবে, কনস্ট্রাক্টর একটি নতুন গ্রাফ নোড তৈরি করে যার উত্তরসূরি হিসাবে সরাসরি এবং ট্রানজিটিভ নোড রয়েছে। এই গ্রাফের ট্রাভার্সালের উপর ভিত্তি করে ডিপসেটগুলির একটি সু-সংজ্ঞায়িত অর্ডারিং শব্দার্থ আছে।

ডিপসেট ব্যবহারের উদাহরণগুলির মধ্যে রয়েছে:

• একটি প্রোগ্রামের লাইব্রেরির জন্য সমস্ত অবজেক্ট ফাইলের পাথ সংরক্ষণ করা, যা তারপর একটি প্রদানকারীর মাধ্যমে একটি লিঙ্কার অ্যাকশনে পাস করা যেতে পারে।

• একটি ব্যাখ্যা করা ভাষার জন্য, ট্রানজিটিভ সোর্স ফাইলগুলি সংরক্ষণ করা হয় যা একটি এক্সিকিউটেবলের রানফাইলে অন্তর্ভুক্ত থাকে।

বর্ণনা এবং অপারেশন

ধারণাগতভাবে, একটি ডিপসেট একটি নির্দেশিত অ্যাসাইক্লিক গ্রাফ (ডিএজি) যা সাধারণত লক্ষ্য গ্রাফের মতো দেখায়। এটি পাতা থেকে মূল পর্যন্ত নির্মিত হয়। একটি নির্ভরতা শৃঙ্খলে প্রতিটি লক্ষ্য তাদের পড়া বা অনুলিপি না করেই আগেরটির উপরে নিজস্ব বিষয়বস্তু যুক্ত করতে পারে।

DAG-এর প্রতিটি নোড সরাসরি উপাদানের একটি তালিকা এবং চাইল্ড নোডের একটি তালিকা ধারণ করে। ডিপসেটের বিষয়বস্তু হল ট্রানজিটিভ উপাদান, যেমন সমস্ত নোডের সরাসরি উপাদান। ডেপসেট কনস্ট্রাক্টর ব্যবহার করে একটি নতুন ডিপসেট তৈরি করা যেতে পারে: এটি সরাসরি উপাদানগুলির একটি তালিকা এবং চাইল্ড নোডগুলির আরেকটি তালিকা গ্রহণ করে।

s = depset(["a", "b", "c"])
t = depset(["d", "e"], transitive = [s])

print(s)    # depset(["a", "b", "c"])
print(t)    # depset(["d", "e", "a", "b", "c"])

একটি ডিপসেটের বিষয়বস্তু পুনরুদ্ধার করতে, to_list() পদ্ধতি ব্যবহার করুন। এটি সমস্ত ট্রানজিটিভ উপাদানগুলির একটি তালিকা প্রদান করে, সদৃশ সহ নয়। DAG এর সুনির্দিষ্ট কাঠামো সরাসরি পরিদর্শন করার কোন উপায় নেই, যদিও এই কাঠামোটি উপাদানগুলি ফেরত দেওয়া ক্রমকে প্রভাবিত করে।

s = depset(["a", "b", "c"])

print("c" in s.to_list())              # True
print(s.to_list() == ["a", "b", "c"])  # True

ডিপসেটে অনুমোদিত আইটেমগুলি সীমাবদ্ধ, ঠিক যেমন অভিধানে অনুমোদিত কীগুলি সীমাবদ্ধ। বিশেষ করে, ডিপসেট বিষয়বস্তু পরিবর্তনযোগ্য নাও হতে পারে।

ডিপসেট রেফারেন্স সমতা ব্যবহার করে: একটি ডেপসেট তার নিজের সমান, কিন্তু অন্য যেকোন ডিপসেটের সাথে অসম, এমনকি যদি তাদের একই বিষয়বস্তু এবং একই অভ্যন্তরীণ গঠন থাকে।

s = depset(["a", "b", "c"])
t = s
print(s == t)  # True

t = depset(["a", "b", "c"])
print(s == t)  # False

d = {}
d[s] = None
d[t] = None
print(len(d))  # 2

তাদের বিষয়বস্তু দ্বারা ডিপসেট তুলনা করতে, তাদের সাজানো তালিকায় রূপান্তর করুন।

s = depset(["a", "b", "c"])
t = depset(["c", "b", "a"])
print(sorted(s.to_list()) == sorted(t.to_list()))  # True

একটি ডিপসেট থেকে উপাদান অপসারণ করার ক্ষমতা নেই। যদি এটি প্রয়োজন হয়, তাহলে আপনাকে অবশ্যই ডিপসেটের সম্পূর্ণ বিষয়বস্তু পড়তে হবে, আপনি যে উপাদানগুলি সরাতে চান তা ফিল্টার করতে হবে এবং একটি নতুন ডেপসেট পুনর্গঠন করতে হবে। এটি বিশেষভাবে কার্যকর নয়।

s = depset(["a", "b", "c"])
t = depset(["b", "c"])

# Compute set difference s - t. Precompute t.to_list() so it's not done
# in a loop, and convert it to a dictionary for fast membership tests.
t_items = {e: None for e in t.to_list()}
diff_items = [x for x in s.to_list() if x not in t_items]
# Convert back to depset if it's still going to be used for union operations.
s = depset(diff_items)
print(s)  # depset(["a"])

অর্ডার

to_list অপারেশন DAG এর উপর একটি ট্রাভার্সাল সঞ্চালন করে। ট্রাভার্সালের ধরন ডিপসেটটি নির্মাণের সময় নির্দিষ্ট করা অর্ডারের উপর নির্ভর করে। এটি Bazel-এর পক্ষে একাধিক অর্ডার সমর্থন করার জন্য দরকারী কারণ কখনও কখনও সরঞ্জামগুলি তাদের ইনপুটগুলির ক্রম সম্পর্কে যত্ন নেয়। উদাহরণস্বরূপ, একটি লিঙ্কার অ্যাকশন নিশ্চিত করতে হতে পারে যে B যদি A এর উপর নির্ভর করে, তাহলে Ao লিঙ্কারের কমান্ড লাইনে Bo এর আগে আসে। অন্যান্য সরঞ্জামগুলির বিপরীত প্রয়োজনীয়তা থাকতে পারে।

তিনটি ট্রাভার্সাল preorder সমর্থিত: postorder , প্রিঅর্ডার এবং topological । প্রথম দুটি ঠিক ট্রি ট্রাভার্সালের মতো কাজ করে যেগুলি ডিএজি-তে কাজ করে এবং ইতিমধ্যে পরিদর্শন করা নোডগুলি এড়িয়ে যায়। তৃতীয় ক্রমটি মূল থেকে পাতা পর্যন্ত একটি টপোলজিকাল বাছাই হিসাবে কাজ করে, মূলত প্রি-অর্ডারের মতোই, ভাগ করা শিশুদের শুধুমাত্র তাদের পিতামাতার পরেই তালিকাভুক্ত করা হয়। প্রি-অর্ডার এবং পোস্টঅর্ডার বাম-থেকে-ডান ট্রাভার্সাল হিসাবে কাজ করে, তবে মনে রাখবেন যে প্রতিটি নোডের মধ্যে সরাসরি উপাদানগুলির বাচ্চাদের সাথে সম্পর্কিত কোনও অর্ডার নেই। টপোলজিকাল অর্ডারের জন্য, কোনও বাম-থেকে-ডান গ্যারান্টি নেই, এমনকি DAG-এর বিভিন্ন নোডে ডুপ্লিকেট উপাদান থাকা ক্ষেত্রেও সমস্ত-পিতা-মাতা-পূর্ব-সন্তানের গ্যারান্টি প্রযোজ্য নয়।

# This demonstrates different traversal orders.

def create(order):
  cd = depset(["c", "d"], order = order)
  gh = depset(["g", "h"], order = order)
  return depset(["a", "b", "e", "f"], transitive = [cd, gh], order = order)

print(create("postorder").to_list())  # ["c", "d", "g", "h", "a", "b", "e", "f"]
print(create("preorder").to_list())   # ["a", "b", "e", "f", "c", "d", "g", "h"]

# This demonstrates different orders on a diamond graph.

def create(order):
  a = depset(["a"], order=order)
  b = depset(["b"], transitive = [a], order = order)
  c = depset(["c"], transitive = [a], order = order)
  d = depset(["d"], transitive = [b, c], order = order)
  return d

print(create("postorder").to_list())    # ["a", "b", "c", "d"]
print(create("preorder").to_list())     # ["d", "b", "a", "c"]
print(create("topological").to_list())  # ["d", "b", "c", "a"]

ট্র্যাভারসালগুলি কীভাবে প্রয়োগ করা হয় তার কারণে, কনস্ট্রাক্টরের order কীওয়ার্ড আর্গুমেন্টের সাথে ডিপসেট তৈরি করার সময় অর্ডারটি অবশ্যই নির্দিষ্ট করতে হবে। যদি এই যুক্তিটি বাদ দেওয়া হয়, ডিপসেটের বিশেষ default অর্ডার থাকে, সেক্ষেত্রে এর কোনো উপাদানের ক্রম সম্পর্কে কোনো গ্যারান্টি নেই (এটি নির্ধারক ছাড়া)।

সম্পূর্ণ উদাহরণ

এই উদাহরণটি https://github.com/bazelbuild/examples/tree/main/rules/depsets এ উপলব্ধ।

ধরুন একটি অনুমানমূলক ব্যাখ্যা করা ভাষা আছে Foo. প্রতিটি foo_binary তৈরি করার জন্য আপনাকে প্রত্যক্ষ বা পরোক্ষভাবে যে সমস্ত *.foo ফাইলের উপর নির্ভর করে তা জানতে হবে।

# //depsets:BUILD

load(":foo.bzl", "foo_library", "foo_binary")

# Our hypothetical Foo compiler.
py_binary(
    name = "foocc",
    srcs = ["foocc.py"],
)

foo_library(
    name = "a",
    srcs = ["a.foo", "a_impl.foo"],
)

foo_library(
    name = "b",
    srcs = ["b.foo", "b_impl.foo"],
    deps = [":a"],
)

foo_library(
    name = "c",
    srcs = ["c.foo", "c_impl.foo"],
    deps = [":a"],
)

foo_binary(
    name = "d",
    srcs = ["d.foo"],
    deps = [":b", ":c"],
)

# //depsets:foocc.py

# "Foo compiler" that just concatenates its inputs to form its output.
import sys

if __name__ == "__main__":
  assert len(sys.argv) >= 1
  output = open(sys.argv[1], "wt")
  for path in sys.argv[2:]:
    input = open(path, "rt")
    output.write(input.read())

এখানে, a , b , c , এবং d এর srcs ক্ষেত্রের সমস্ত *.foo ফাইলের বাইনারি d এর ট্রানজিটিভ সোর্স। foo_binary টার্গেটের জন্য d.foo ছাড়াও যেকোন ফাইল সম্পর্কে জানার জন্য, foo_library টার্গেটগুলিকে একটি প্রোভাইডারের কাছে পাস করতে হবে। প্রতিটি লাইব্রেরি তার নিজস্ব নির্ভরতা থেকে প্রদানকারীদের গ্রহণ করে, তার নিজস্ব তাত্ক্ষণিক উত্স যোগ করে এবং বর্ধিত বিষয়বস্তু সহ একটি নতুন প্রদানকারীকে পাস করে। foo_binary নিয়ম একই কাজ করে, একটি প্রদানকারীকে ফেরত দেওয়ার পরিবর্তে, এটি একটি কর্মের জন্য একটি কমান্ড লাইন তৈরি করতে উত্সগুলির সম্পূর্ণ তালিকা ব্যবহার করে।

এখানে foo_library এবং foo_binary নিয়মগুলির সম্পূর্ণ বাস্তবায়ন রয়েছে।

# //depsets/foo.bzl

# A provider with one field, transitive_sources.
FooFiles = provider(fields = ["transitive_sources"])

def get_transitive_srcs(srcs, deps):
  """Obtain the source files for a target and its transitive dependencies.

  Args:
    srcs: a list of source files
    deps: a list of targets that are direct dependencies
  Returns:
    a collection of the transitive sources
  """
  return depset(
        srcs,
        transitive = [dep[FooFiles].transitive_sources for dep in deps])

def _foo_library_impl(ctx):
  trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
  return [FooFiles(transitive_sources=trans_srcs)]

foo_library = rule(
    implementation = _foo_library_impl,
    attrs = {
        "srcs": attr.label_list(allow_files=True),
        "deps": attr.label_list(),
    },
)

def _foo_binary_impl(ctx):
  foocc = ctx.executable._foocc
  out = ctx.outputs.out
  trans_srcs = get_transitive_srcs(ctx.files.srcs, ctx.attr.deps)
  srcs_list = trans_srcs.to_list()
  ctx.actions.run(executable = foocc,
                  arguments = [out.path] + [src.path for src in srcs_list],
                  inputs = srcs_list + [foocc],
                  outputs = [out])

foo_binary = rule(
    implementation = _foo_binary_impl,
    attrs = {
        "srcs": attr.label_list(allow_files=True),
        "deps": attr.label_list(),
        "_foocc": attr.label(default=Label("//depsets:foocc"),
                             allow_files=True, executable=True, cfg="host")
    },
    outputs = {"out": "%{name}.out"},
)

আপনি এই ফাইলগুলিকে একটি নতুন প্যাকেজে অনুলিপি করে, যথাযথভাবে লেবেলগুলির নাম পরিবর্তন করে, ডামি সামগ্রী সহ উত্স *.foo ফাইল তৈরি করে এবং d লক্ষ্য তৈরি করে এটি পরীক্ষা করতে পারেন।

কর্মক্ষমতা

ডিপসেট ব্যবহারের অনুপ্রেরণা দেখতে, get_transitive_srcs() একটি তালিকায় এর উত্স সংগ্রহ করলে কী হবে তা বিবেচনা করুন।

def get_transitive_srcs(srcs, deps):
  trans_srcs = []
  for dep in deps:
    trans_srcs += dep[FooFiles].transitive_sources
  trans_srcs += srcs
  return trans_srcs

এটি সদৃশগুলিকে বিবেচনায় নেয় না, তাই a-এর সোর্স ফাইলগুলি কমান্ড লাইনে দুইবার এবং আউটপুট ফাইলের বিষয়বস্তুতে দুইবার a হবে।

একটি বিকল্প হল একটি সাধারণ সেট ব্যবহার করা, যা একটি অভিধান দ্বারা অনুকরণ করা যেতে পারে যেখানে কীগুলি উপাদান এবং সমস্ত কীগুলি True তে মানচিত্র।

def get_transitive_srcs(srcs, deps):
  trans_srcs = {}
  for dep in deps:
    for file in dep[FooFiles].transitive_sources:
      trans_srcs[file] = True
  for file in srcs:
    trans_srcs[file] = True
  return trans_srcs

এটি সদৃশ থেকে পরিত্রাণ পায়, তবে এটি কমান্ড লাইন আর্গুমেন্টের ক্রম (এবং ফাইলের বিষয়বস্তু) অনির্দিষ্ট করে তোলে, যদিও এখনও নির্ধারক।

তদুপরি, উভয় পন্থাই ডিপসেট-ভিত্তিক পদ্ধতির চেয়ে লক্ষণগতভাবে খারাপ। যেখানে Foo লাইব্রেরির উপর নির্ভরশীলতার একটি দীর্ঘ শৃঙ্খল রয়েছে সেই ক্ষেত্রে বিবেচনা করুন। প্রতিটি নিয়ম প্রসেস করার জন্য একটি নতুন ডেটা স্ট্রাকচারে এর আগে আসা সমস্ত ট্রানজিটিভ সোর্স কপি করতে হবে। এর মানে হল যে একটি পৃথক লাইব্রেরি বা বাইনারি লক্ষ্য বিশ্লেষণের জন্য সময় এবং স্থান খরচ চেইনের নিজস্ব উচ্চতার সমানুপাতিক। n দৈর্ঘ্যের একটি চেইন, foolib_1 ← foolib_2 ← … ← foolib_n, সামগ্রিক খরচ কার্যকরভাবে O(n^2)।

সাধারণভাবে বলতে গেলে, যখনই আপনি আপনার ট্রানজিটিভ নির্ভরতার মাধ্যমে তথ্য সংগ্রহ করছেন তখনই ডিপসেট ব্যবহার করা উচিত। এটি নিশ্চিত করতে সাহায্য করে যে আপনার বিল্ড স্কেল এবং আপনার টার্গেট গ্রাফ আরও গভীর হয়।

অবশেষে, নিয়ম বাস্তবায়নে অপ্রয়োজনীয়ভাবে ডিপসেটের বিষয়বস্তু পুনরুদ্ধার না করা গুরুত্বপূর্ণ। একটি বাইনারি নিয়মের শেষে to_list() -এ একটি কল ঠিক আছে, যেহেতু সামগ্রিক খরচ শুধুমাত্র O(n)। যখন অনেক নন-টার্মিনাল টার্গেট to_list() কল করার চেষ্টা করে তখন চতুর্মুখী আচরণ ঘটে।

ডিপসেটগুলি দক্ষতার সাথে ব্যবহার করার বিষয়ে আরও তথ্যের জন্য, কর্মক্ষমতা পৃষ্ঠাটি দেখুন।

API রেফারেন্স

আরো বিস্তারিত জানার জন্য এখানে দেখুন.