הבלוג של גרי רשף

03/10/2010

החור הראשון

Filed under: Uncategorized — תגיות: , , , — גרי רשף @ 21:30

הלו- מה זה? אתה בענייני SQL או….?..
קודם כל להירגע (ככתוב בספר בישול ידוע): בסך הכל שאלו אותי בעבודה כיצד למצוא בטבלה עם עמודת מספרים את הערך הראשון שחסר, הווה אומר- החור הראשון ברצף.
את הפטנט למדתי לפני שנים מאיציק בן גן: מבצעים Left Join של הטבלה עם עצמה לפי N=N+1 (כלומר– לכל שורה נתאים את הבאה אחריה), נחפש את אלו להם לא נמצאה התאמה, נבצע Top 1 כי מעוניינים בראשון, ולא נשכח להוסיף 1 לערך שקיבלנו (הרי לא מצאנו את הראשון שחסר אלא את האחרון שאינו חסר..).
ניצור טבלת מספרים בת כמיליון שורות, ונשמיט ברשלנותנו מספר ערכים בדרך:

Create Table #T(I Int Primary Key);

Go


With T As

(Select 1 N

Union All

Select    N+1

From    T

Where    N<1000000)

Insert Into    #T

Select    N

From    T

Where    N%1999<>0

Option (MaxRecursion 0);

Go

וכעת נמצא את החור הראשון (מן הסתם 1999 שהוא הראשון שדילגתי מעליו):

Select    Top 1 T1.I+1

From    #T T1

Left Join #T T2

        On T1.I+1=T2.I

Where    T2.I Is Null;

Go

בדרך הביתה בפקקים הירהרתי בנושא ועלתה בדעתי דרך נוספת- גם היא בזכות פטנט שלמדתי מבן גן (ושאתייחס אליו בצרה בסוף):

Select    Max(I)+1

From    (Select    Row_Number() Over(Order By I) Mispar,

                (Select Min(I) From #T) Mn,

                *

        From    #T) T

Where    I-Mn-Mispar=-1;

Go

אם נחסיר מכל מספר (עמודה I) את מספרו הסידורי (העמודה המחושבת Mispar) – לכל רצף תהיה אותה תוצאה עד החור שבסופה, וכדי לזהות את הרצף הראשון נחסר מהתוצאה את I המינימלי ואז היא תהיה שווה 1- (ברצף הראשון), וכעת נמצא את האחרון ברצף על ידי Max ונוסיף לו 1..

(ההסבר קצת מסורבל ואולי הרקע בהמשך יבהיר את הנושא)

למי שתוהה מדוע חישבתי את המינימום בעזרת שאילתת משנה ולא בעזרת פונקציית חלון ()Min(I) Over – להפתעתי דרך זו יעילה יותר!

איזו שיטה יותר יעילה?

image

הדרך השניה יעילה יותר.

שתי הערות:

1. אם עמודת המספרים לא תהיה מאונדקסת – הדרך הראשונה תהיה יעילה יותר באופן משמעותי, אבל אני מניח שעמודות מספור מאונדקסות בדרך כלל.

2. אם אשנה את השיטה השניה- אציב את המינימום במשתנה, ואז אריץ את השליפה (כדי לחסוך את העלות של ה-Nested Loops) – היא תהיה יעילה פי שניים (בהנחה שיש אינדקס)! לי זה נראה קצת מוזר וגם לא ברור לי מדוע ה-Nested Loops כל כך יקרים כשמדובר ב-Join בין סט לבין ערך בודד.

אגב- אם המונח "חור" יתייחס גם להיעדרו של המספר הראשון – 1 – מהרצף, אזי בעזרת השיטה הראשונה לא נמצא אותו, ובעזרת שינוי קוסמטי קטן בשיטה השניה – כן:

Select    IsNull(Max(I),0)+1

From    (Select    Row_Number() Over(Order By I) Mispar,

                (Select Min(I) From #T) Mn,

                *

        From    #T) T

Where    I-Mispar=0;

Go

האם יש דרך יעילה יותר? אינני יודע אם יש, אך אולי תהיה: אם איציק בן גן יצליח בקמפיין שלו להשבחת פונקציות החלון של SQL Server – בעזרת פונקציית Lead נוכל למצוא בקלות וביעילות את המספר הראשון שה-Lead (העוקב) שלו גדול ממנו ביותר מ-1.

הרקע לדרך השניה הוא פטנט יפה לחלוקת טור של מספרים לא רציפים לרצפים. נניח הטור 1,2,3,8,10,11 מתחלק לשלושה רצפים: (10,11) (8) (1,2,3).

השיטה היא ליצור עמודת מספרים מחושבת ..1,2,3,4 , להחסיר מכל מספר את המספר המחושב שלו, ואז לכל רצף תהיה תוצאה זהה: מהמספרים 1,2,3 נחסיר 1,2,3 בהתאמה ונקבל 0,0,0; מ-8 נחסיר את 4 (הוא המספר הרביעי בסדר) ונקבל 4; ומ-10,11 נחסיר 5,6 בהתאמה ונקבל 5,5.

מודעות פרסומת

להגיב »

עדיין אין תגובות.

RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

הזינו את פרטיכם בטופס, או לחצו על אחד מהאייקונים כדי להשתמש בחשבון קיים:

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

בלוג בוורדפרס.קום.

%d בלוגרים אהבו את זה: