ከጥቂት ቀናት በፊት ተከስቷል። የሃይድራ ኮንፈረንስ. ከ JUG.ru ቡድን የመጡት ሰዎች ህልም ተናጋሪዎችን (ሌስሊ ላምፖርት! ክሊፍ ክሊክ! ማርቲን ክሌፕማን!) ጋብዘው ለሁለት ቀናት ለተከፋፈሉ ስርዓቶች እና ኮምፒውተሮች አሳልፈዋል። ኮንቱር ከጉባኤው ሶስት አጋሮች አንዱ ነበር። በዳስ ውስጥ ተነጋገርን፣ ስለ ተከፋፈለው ማከማቻ ተነጋገርን፣ ቢንጎን ተጫወትን፣ እና እንቆቅልሾችን ፈታን።

ይህ በኮንቱር ላይ የተግባር ትንተና ከጽሑፋቸው ደራሲ የተገኘ ልጥፍ ነው። በሃይድራ ላይ ማን ነበር - ይህ አስደሳች ተሞክሮ ለማስታወስ የእርስዎ ምክንያት ነው, ማን አልነበረም - አንጎልዎን ለመዘርጋት እድል ትልቅ ኦ- ማስታወሻ.

ውሳኔያቸውን ለመጻፍ ገለጻውን ወደ ስላይድ የፈረሱ ተሳታፊዎችም ነበሩ። እየቀለድኩ አይደለም - ይህንን የተቆለለ ወረቀት ለማረጋገጫ አስረከቡ፡-

በአጠቃላይ ሦስት ተግባራት ነበሩ፡-

• ለጭነት ማመጣጠን ቅጂዎችን በክብደት ስለ መምረጥ
• የጥያቄ ውጤቶችን በማህደረ ትውስታ ዳታቤዝ ላይ ስለመደርደር
• ቀለበት ቶፖሎጂ ጋር በተሰራጨ ሥርዓት ውስጥ ግዛት ማስተላለፍ ላይ

ተግባር 1. ክላስተር ደንበኛ

K ከ N ክብደት የተከፋፈለ ስርዓት ግልባጮችን በብቃት ለመምረጥ ስልተ ቀመር ማቅረብ አስፈላጊ ነበር፡-

ቡድንዎ በጅምላ ለተሰራጨ የኤን ኖዶች የደንበኛ ቤተ-መጽሐፍት የማዘጋጀት ኃላፊነት ተሰጥቶታል። ቤተ መፃህፍቱ ከአንጓዎች ጋር የተያያዙ የተለያዩ ሜታዳታዎችን ይከታተላል (ለምሳሌ፣ የቆይታ ጊዜያቸው፣ 4xx/5xx ምላሽ ተመኖች፣ ወዘተ.) እና ተንሳፋፊ ነጥብ ክብደቶችን W1..WN ለእነሱ ይመድባል። በተመሳሳይ ጊዜ ያለውን የማስፈጸሚያ ስልት ለመደገፍ ቤተ መፃህፍቱ የK of N ኖዶችን በዘፈቀደ መምረጥ መቻል አለበት - የመመረጥ እድሉ ከአንጓው ክብደት ጋር ተመጣጣኝ መሆን አለበት።

አንጓዎችን በብቃት ለመምረጥ አልጎሪዝም ያቅርቡ። ትልቅ O notation በመጠቀም የሒሳብ ውስብስብነቱን ይገምቱ።

ለምንድነው ሁሉም ነገር በእንግሊዝኛ የሆነው?

ምክንያቱም በዚህ መልክ የኮንፈረንሱ ተሳታፊዎች ከእነርሱ ጋር ተዋግተዋል እና እንግሊዘኛ የሃይድራ ኦፊሴላዊ ቋንቋ ስለሆነ። ተግባሮቹ ይህን ይመስሉ ነበር፡-

ወረቀት እና እርሳስ ይውሰዱ, ያስቡ, ወዲያውኑ አጥፊዎችን ለመክፈት አይቸኩሉ 🙂

የመፍትሄው ትንተና (ቪዲዮ)

ከ5፡53 ጀምሮ 4 ደቂቃ ብቻ፡-

እና ፊሊፕ ቻርት የያዙት ሰዎች መፍትሄቸውን እንዴት እንዳስቀመጡት እነሆ፡-

የመፍትሄው ትንተና (ጽሑፍ)

የሚከተለው መፍትሔ በላዩ ላይ ነው፡ የሁሉም ቅጂዎች ክብደቶች ይደምሩ፣ የዘፈቀደ ቁጥር ከ 0 እስከ የክብደቶች ድምር ያመነጩ፣ ከዚያ የi-replica ይምረጡ የክብደት ድምር ከ 0 እስከ (i-1) ኛ ከዘፈቀደ ቁጥር ያነሰ ነው, እና የተባዛ ክብደቶች ድምር ከ 0 እስከ i-th - ከእሱ የበለጠ. ስለዚህ አንድ ቅጂ ለመምረጥ የሚቻል ይሆናል, እና ቀጣዩን ለመምረጥ, የተመረጠውን ቅጂ ግምት ውስጥ ሳያስገባ አጠቃላይ ሂደቱን መድገም ያስፈልግዎታል. በእንደዚህ ዓይነት ስልተ-ቀመር አንድ ቅጂ የመምረጥ ውስብስብነት O (N) ነው, የ K ቅጂዎችን የመምረጥ ውስብስብነት O (N K) ~ O (N2) ነው.

ኳድራቲክ ውስብስብነት መጥፎ ነው, ነገር ግን ሊሻሻል ይችላል. ይህንን ለማድረግ, እንገነባለን ክፍል ዛፍ ለክብደት ድምር። የዛፉ ጥልቀት lg N ይገኛል, በቅጠሎቻቸው ውስጥ ግልባጭ ክብደቶች ይኖራሉ, እና በቀሪዎቹ አንጓዎች - ከፊል ድምር, በዛፉ ሥር ላይ እስከ ሁሉም የክብደት መጠኖች ድረስ. በመቀጠልም የዘፈቀደ ቁጥር ከ 0 ወደ ሁሉም የክብደት ድምር እንፈጥራለን, i-th ቅጂን እናገኛለን, ከዛፉ ላይ እናስወግደዋለን እና የቀሩትን ቅጂዎች ለማግኘት ሂደቱን መድገም. በዚህ ስልተ-ቀመር ዛፍን የመገንባት ውስብስብነት O(N) ሲሆን i-th ቅጂውን የማግኘት እና ከዛፉ ላይ የማስወገድ ውስብስብነት O(lg N) ሲሆን የ K ቅጂዎችን የመምረጥ ውስብስብነት O(N + K) ነው። lg N) ~ ኦ(N lg N) .

የመስመራዊ-ሎግ ውስብስብነት ከኳድራቲክ ውስብስብነት የተሻለ ነው፣በተለይ ለትልቅ ኬ.

ይህ አልጎሪዝም ነው በኮድ ውስጥ ተተግብሯል የክላስተር ደንበኛ ቤተ መጻሕፍት ከፕሮጀክቱ "ምስራቅ". (እዛው, ዛፉ በ O (N lg N) ውስጥ ተገንብቷል, ነገር ግን ይህ የመጨረሻውን የአልጎሪዝም ውስብስብነት አይጎዳውም.)

ተግባር 2. የሜዳ አህያ

በዘፈቀደ መረጃ ጠቋሚ በሌለው መስክ በማህደረ ትውስታ ውስጥ ሰነዶችን በብቃት ለመደርደር ስልተ ቀመር ማቅረብ አስፈላጊ ነበር፡-

የእርስዎ ቡድን የተከፋፈለ የማህደረ ትውስታ ሰነድ ዳታቤዝ የማዘጋጀት ኃላፊነት ተሰጥቶታል። የተለመደው የሥራ ጫና በዘፈቀደ (በመረጃ ያልተደገፈ) የቁጥር መስክ ከ M (አብዛኛውን ጊዜ N <100 << M) የተደረደሩ ከፍተኛ N ሰነዶችን መምረጥ ነው። ትንሽ ያነሰ የተለመደ የሥራ ጫና ከፍተኛ S ሰነዶችን (S ~ N) ከዘለለ በኋላ ከፍተኛ N መምረጥ ነው።

እንደዚህ ያሉ ጥያቄዎችን በብቃት ለማከናወን ስልተ ቀመር ያቅርቡ። በአማካይ ጉዳይ ላይ ትልቅ O notation እና በጣም መጥፎ ሁኔታዎችን በመጠቀም የሂሳብ ውስብስብነቱን ይገምቱ።

የመፍትሄው ትንተና (ቪዲዮ)

ከ34፡50 ጀምሮ፣ 6 ደቂቃ ብቻ፡-

የመፍትሄው ትንተና (ጽሑፍ)

የገጽታ መፍትሄ፡ ሁሉንም ሰነዶች መደርደር (ለምሳሌ በ ፈጣን), ከዚያ N + S ሰነዶችን ይውሰዱ. በዚህ ሁኔታ, የመደርደር ውስብስብነት በአማካይ O (M lg M), በከፋ O (M2) ላይ ነው.

ሁሉንም M ሰነዶች መደርደር እና ትንሽ ክፍል ብቻ መውሰድ ውጤታማ እንዳልሆነ ግልጽ ነው. ሁሉንም ሰነዶች ላለመደርደር, አልጎሪዝም ተስማሚ ነው በፍጥነት መምረጥ, የሚፈለጉትን ሰነዶች N + S ይመርጣል (በማንኛውም ስልተ ቀመር ሊደረደሩ ይችላሉ). በዚህ ሁኔታ, ውስብስብነቱ በአማካይ ወደ O (M) ይቀንሳል, በጣም የከፋው ሁኔታ ግን ተመሳሳይ ነው.

ሆኖም ግን, የበለጠ በብቃት ሊያደርጉት ይችላሉ - አልጎሪዝምን ይጠቀሙ ሁለትዮሽ ክምር ዥረት. በዚህ ሁኔታ, የመጀመሪያዎቹ N + S ሰነዶች ወደ min- ወይም max-heap ተጨምረዋል (እንደየዓይነት አቅጣጫው ይወሰናል), ከዚያም እያንዳንዱ ቀጣይ ሰነድ አሁን ያለውን ዝቅተኛ ወይም ከፍተኛ ሰነድ ከያዘው የዛፉ ሥር ጋር ይነጻጸራል. እና አስፈላጊ ከሆነ በዛፉ ላይ ይጨመራል. በዚህ ሁኔታ, በጣም በከፋ ሁኔታ ውስጥ ያለው ውስብስብነት, ዛፉን ያለማቋረጥ እንደገና መገንባት ሲኖርብዎት, O (M lg M) ነው, ውስብስብነቱ በአማካይ O (M) ነው, ልክ እንደ ፈጣን ምርጫ.

ነገር ግን፣ ክምር ዥረት የበለጠ ቀልጣፋ ሆኖ የተገኘው በተግባር አብዛኛው ሰነዶች ከስር ኤለመንቱ ጋር አንድ ጊዜ በማነፃፀር ክምሩን እንደገና ሳይገነቡ መጣል ስለሚቻል ነው። እንዲህ ዓይነቱ መደርደር በኮንቱር ውስጥ በተዘጋጀው እና ጥቅም ላይ የዋለው በዜብራ ውስጠ-ማህደረ ትውስታ ሰነድ ዳታቤዝ ውስጥ ተተግብሯል።

ተግባር 3. የግዛት መለዋወጥ

ግዛቶችን ለመለወጥ በጣም ቀልጣፋውን ስልተ-ቀመር ሀሳብ ማቅረብ አስፈላጊ ነበር-

ቡድንዎ ለተከፋፈለ የN nodes ክላስተር የሚያምር የግዛት ልውውጥ ዘዴን የማዘጋጀት ኃላፊነት ተሰጥቶታል። የ i-th node ግዛት ወደ (i+1) -ኛ መስቀለኛ መንገድ መተላለፍ አለበት፣ N-th node's state ወደ መጀመሪያው መስቀለኛ መንገድ መተላለፍ አለበት። የሚደገፈው ክዋኔ ሁለት አንጓዎች ግዛቶቻቸውን በአቶሚክ ሲለዋወጡ የግዛት መለዋወጥ ነው። የስቴት ስዋፕ ኤም ሚሊሰከንዶች እንደሚወስድ ይታወቃል። እያንዳንዱ መስቀለኛ መንገድ በማንኛውም ጊዜ በነጠላ ግዛት መለዋወጥ ላይ መሳተፍ ይችላል።

የሁሉንም አንጓዎች ግዛቶች በክላስተር ውስጥ ለማስተላለፍ ምን ያህል ጊዜ ይወስዳል?

የመፍትሄው ትንተና (ጽሑፍ)

የገጽታ መፍትሄ-የመጀመሪያውን እና የሁለተኛውን ኤለመንቱን ግዛቶች, ከዚያም የመጀመሪያውን እና ሶስተኛውን, ከዚያም የመጀመሪያውን እና አራተኛውን, ወዘተ. ከእያንዳንዱ ልውውጥ በኋላ የአንድ አካል ሁኔታ በሚፈለገው ቦታ ላይ ይሆናል. O(N) permutations ማድረግ እና O(N M) ጊዜ ማሳለፍ አለቦት።

የመስመር ጊዜ ረጅም ነው ፣ ስለሆነም የንጥረ ነገሮችን ሁኔታ በጥንድ መለወጥ ይችላሉ-የመጀመሪያው ከሁለተኛው ፣ ሦስተኛው ከአራተኛው ፣ ወዘተ. ከእያንዳንዱ የግዛት ልውውጥ በኋላ, እያንዳንዱ ሁለተኛ አካል በትክክለኛው ቦታ ላይ ይሆናል. የ O(lg N) ማስተላለፎችን ማድረግ እና የ O(M lg N) ጊዜ ማሳለፍ አለቦት።

ሆኖም ፈረቃውን የበለጠ ውጤታማ ማድረግ ይቻላል - በመስመር ላይ ሳይሆን በቋሚ ጊዜ። ይህንን ለማድረግ በመጀመሪያ ደረጃ የመጀመሪያውን ኤለመንቱን ሁኔታ ከመጨረሻው ጋር, ሁለተኛውን ከፔንታል እና ወዘተ ጋር መለዋወጥ ያስፈልግዎታል. የመጨረሻው ንጥረ ነገር ሁኔታ በትክክለኛው ቦታ ላይ ይሆናል. እና አሁን የሁለተኛውን ንጥረ ነገር ሁኔታ ከኋለኛው ጋር ፣ ሦስተኛው ከፔኑቲሜት ፣ ወዘተ ጋር መለዋወጥ አለብን። ከዚህ ዙር ልውውጥ በኋላ, የሁሉም ንጥረ ነገሮች ግዛቶች በትክክለኛው ቦታ ላይ ይሆናሉ. በአጠቃላይ O(2M) ~ O(1) ማስተላለፎች ይኖራሉ።

እንዲህ ዓይነቱ መፍትሔ መሽከርከር የሁለት ዘንግ ሲምሜትሮች ጥንቅር መሆኑን አሁንም የሚያስታውሰውን የሂሳብ ሊቅ በጭራሽ አያስገርምም። በነገራችን ላይ, በጥቃቅንነት በአጠቃላይ ለአንድ ፈረቃ አይደለም, ነገር ግን በ K <N አቀማመጥ. (በአስተያየቶቹ ውስጥ በትክክል እንዴት ይፃፉ)

እንቆቅልሾችን ወደውታል? ሌሎች መፍትሄዎችን ታውቃለህ? በአስተያየቶቹ ውስጥ ያካፍሉ.

እና በመጨረሻ አንዳንድ ጠቃሚ አገናኞች እዚህ አሉ

• ስለ ተጨማሪ ይወቁ የመሠረተ ልማት ግንባታ ኮንቱር ውስጥ
• የውስጥ መዝገቦችን ይመልከቱ በራሪ ወረቀት ከሪፖርቶች ጋር ስለ ተከፋፈሉ ስርዓቶች
• ተከታታይ የቪዲዮ ትምህርቶችን ይመልከቱለተራ ሰዎች ያልተለመዱ ስልተ ቀመሮች»
• ሰብስክራይብ ያድርጉን በቴሌግራም ቻናል

ምንጭ: hab.com