محمد سلیم آبادی
شنبه 17 اردیبهشت 1390, 01:23 صبح
مقدمه
مساله زیر را جهت تقویت مهارت های SQL برنامه نویسان طراحی کرده ام.
راه حل باید دارای شرایط زیر باشد:
استاندارد بوده به این معنا که از Syntax هایی که مخصوص RDBMS های مختلف هست استفاده نشده باشد. این ویژگی باعث می شود راه حل قابل حمل (Portable) شود و در نرم افزارهایی که طبق استاندارد های SQL کار می کنند قابل اجرا شود.
راه حل تنها از یک عبارت SELECT تشکیل شده باشد.
حق استفاده از View یا Common Table Expression وجود ندارد.
استفاده از توابع Ranking ممنوع است.
هدف ارائه کوتاه ترین راه حل است.
پس کوتاه ترین راه حل به عنوان راه حل برنده شناخته خواهد شد. از راه حل هایی که دوستان ارسال می کنند استقبال خواهد شد. 7 روز دیگر من راه حل های خودم را همراه با راه حلهایی که دوستان ارسال کردند (در صورت ارسال) را انتشار خواهم داد.
مساله
فروشگاهی را در نظر بگیرید که تعدادی فروشنده در آن کار می کنند. فروشندگان در تمام روزهای سال مشغول به کار نیستند و ممکن است روزهای تعطیل فروشگاه بسته شود یا اینکه در ایام غیر تعطیل فروشنده به مرخصی رود.
مدیر فروشگاه قصد دارد جهت تشویق کارکنان خود افرادی را که 5 روز کاری، بطور متوالی توانسته اند فروش صعودی مطلق داشته باشند را مورد تشویق نقدی قرار دهد.
منظور از فروش صعودی مطلق این است که فروش روز بعد از فروش روز قبل بیشتر بوده (حتی برابر هم نباشد) و فروش روز سوم از روز دوم بیشتر بوده و همینطور تا 5 روز.
این 5 روز باید 5 روز متوالی کاری فرد بوده باشد. به این معنا که می تواند بین این 5 روز، روزهایی باشد که فرد به مرخصی رفته باشد یا اینکه آن روزها تعطیل بوده باشند.
به نمودار دو بعدی زیر دقت کنید:
69819
کاربر (فروشنده) ای که با رنگ قرمز مشخص شده است به عنوان نتیجه باید اعلام شود. به دلیل اینکه توانسته 5 روز متوالی کاری موفق به فروش صعودی مطلق شود. یعنی فروش روز پانزدهم از روز دوازدهم بیشتر بوده و فروش روز شانزدهم از پانزدهم بیشتر همینطور تا روز بیستم.
روزهای 13و 14و 18 این فرد مشغول کار نبوده است و مشکلی هم در روال کار بوجود نیامده است. اگر روزی که بوده باشد و کاری انجام نداده باشد فروش صفر برای فرد در نظر گرفته می شود مثل روز 21 یکم کاربری که با رنگ آبی مشخص شده است.
برای ذخیره کردن این اطلاعات جدول زیر را در نظر گرفته ایم:
CREATE TABLE Sales
(user_nbr INTEGER NOT NULL,
day_nbr INTEGER NOT NULL
CHECK(day_nbr BETWEEN 1 AND 365),
Value INTEGER NOT NULL
CHECK(value >= 0),
PRIMARY KEY (user_nbr, day_nbr));
حالا قصد ما این است که توسط یک SELECT تنها لیست افرادی را بدست آوریم که دارای شرط ما باشند. نکته اینکه ممکن است یک فرد در چند توالی فروش صعودی داشته باشد ولی یکبار بیشتر نمی خواهیم نام فرد انتخاب شود. مثلا از روز پنجم تا نهم پنج روز متوالی فروش صعودی داشته است و همچنین در روز بیستم تا بیست هشتم بازهم 5 روز متوالی فروش صعودی داشته است.
داده های آزمایشی را برای تست راه حلتان استفاده کنید. جواب باید 1 باشد.
INSERT INTO Sales
VALUES (1, 12, 60),
(1, 15, 70),
(1, 16, 80),
(1, 17, 83),
(1, 19, 86),
(1, 20, 90),
(1, 21, 90),
(2, 12, 80),
(2, 13, 70),
(2, 14, 70),
(2, 17, 50),
(2, 18, 60),
(2, 19, 70),
(2, 20, 80),
(2, 21, 0),
(3, 12, 70),
(3, 13, 60),
(3, 14, 50),
(3, 15, 60),
(3, 16, 60),
(3, 17, 65),
(3, 21, 65),
(4, 1, 5),
(4, 2, 6),
(4, 3, 6),
(4, 4, 7),
(4, 5, 8),
(5, 1, 1),
(5, 2, 2),
(5, 3, 3);
راه حل ها
اولین راه حل توسط آقای رضا یاراحمدی پیشنهاد شد. روشی که معرفی شد توسط ایشان سطر جاری را با 4 سطر بعدی (بر اساس نزدیک ترین روز) اتصال می داد و در صورتی که 5 مقدار به ترتیب از همدیگر بزرگتر بودند در خروجی اعلام می شد. و از آنجایی که ممکن بود فردی در بیش از 5 روز فروش صعودی داشته باشد یا اینکه در دو بازه ی زمانی جدا از هم 5 روز فروش صعودی داشته باشد از کلید واژه ی DISITNCT استفاده شده بود تا فروشنده های تکراری را حذف کند.
subquery های وابسته قطعا هزینه ی بالایی را به سیستم تحمیل می کرد و همچنین هزینه توسعه ی این روش بسیار بالا بود و به عبارتی قابل تعمیم به سختی بود. و برای مقادیر متغیر قابل استفاده نبود.
دومین روش توسط آقای صادقیان مطرح شد. ایده، ایده ی خوبی بود ولی متاسفانه مساله را به درستی حل نمیکرد و پشت سر هم بودن روزها در این راه حل در نظر گرفته نمی شد. ولی در کل تلاش قابل تحسینی بود.
و در انتها آخرین روشی که ارسال کردم کوتاه ترین روش بود. که اگر با این دیدگاه کلاسیک از همان ابتدا به مساله نگاه میشد این راه حل تولید میشد:
راه حل برنده
/*Msalim 4: 238 Chars*/
SELECT DISTINCT user_nbr
FROM Sales S
WHERE (SELECT COUNT(*)
FROM Sales D
WHERE S.user_nbr = user_nbr
AND S.day_nbr < day_nbr
AND S.value < value
AND NOT EXISTS
(SELECT *
FROM Sales
WHERE user_nbr = S.user_nbr
AND day_nbr > S.day_nbr AND day_nbr < D.day_nbr
AND value <= S.value)) >= 5;
مساله زیر را جهت تقویت مهارت های SQL برنامه نویسان طراحی کرده ام.
راه حل باید دارای شرایط زیر باشد:
استاندارد بوده به این معنا که از Syntax هایی که مخصوص RDBMS های مختلف هست استفاده نشده باشد. این ویژگی باعث می شود راه حل قابل حمل (Portable) شود و در نرم افزارهایی که طبق استاندارد های SQL کار می کنند قابل اجرا شود.
راه حل تنها از یک عبارت SELECT تشکیل شده باشد.
حق استفاده از View یا Common Table Expression وجود ندارد.
استفاده از توابع Ranking ممنوع است.
هدف ارائه کوتاه ترین راه حل است.
پس کوتاه ترین راه حل به عنوان راه حل برنده شناخته خواهد شد. از راه حل هایی که دوستان ارسال می کنند استقبال خواهد شد. 7 روز دیگر من راه حل های خودم را همراه با راه حلهایی که دوستان ارسال کردند (در صورت ارسال) را انتشار خواهم داد.
مساله
فروشگاهی را در نظر بگیرید که تعدادی فروشنده در آن کار می کنند. فروشندگان در تمام روزهای سال مشغول به کار نیستند و ممکن است روزهای تعطیل فروشگاه بسته شود یا اینکه در ایام غیر تعطیل فروشنده به مرخصی رود.
مدیر فروشگاه قصد دارد جهت تشویق کارکنان خود افرادی را که 5 روز کاری، بطور متوالی توانسته اند فروش صعودی مطلق داشته باشند را مورد تشویق نقدی قرار دهد.
منظور از فروش صعودی مطلق این است که فروش روز بعد از فروش روز قبل بیشتر بوده (حتی برابر هم نباشد) و فروش روز سوم از روز دوم بیشتر بوده و همینطور تا 5 روز.
این 5 روز باید 5 روز متوالی کاری فرد بوده باشد. به این معنا که می تواند بین این 5 روز، روزهایی باشد که فرد به مرخصی رفته باشد یا اینکه آن روزها تعطیل بوده باشند.
به نمودار دو بعدی زیر دقت کنید:
69819
کاربر (فروشنده) ای که با رنگ قرمز مشخص شده است به عنوان نتیجه باید اعلام شود. به دلیل اینکه توانسته 5 روز متوالی کاری موفق به فروش صعودی مطلق شود. یعنی فروش روز پانزدهم از روز دوازدهم بیشتر بوده و فروش روز شانزدهم از پانزدهم بیشتر همینطور تا روز بیستم.
روزهای 13و 14و 18 این فرد مشغول کار نبوده است و مشکلی هم در روال کار بوجود نیامده است. اگر روزی که بوده باشد و کاری انجام نداده باشد فروش صفر برای فرد در نظر گرفته می شود مثل روز 21 یکم کاربری که با رنگ آبی مشخص شده است.
برای ذخیره کردن این اطلاعات جدول زیر را در نظر گرفته ایم:
CREATE TABLE Sales
(user_nbr INTEGER NOT NULL,
day_nbr INTEGER NOT NULL
CHECK(day_nbr BETWEEN 1 AND 365),
Value INTEGER NOT NULL
CHECK(value >= 0),
PRIMARY KEY (user_nbr, day_nbr));
حالا قصد ما این است که توسط یک SELECT تنها لیست افرادی را بدست آوریم که دارای شرط ما باشند. نکته اینکه ممکن است یک فرد در چند توالی فروش صعودی داشته باشد ولی یکبار بیشتر نمی خواهیم نام فرد انتخاب شود. مثلا از روز پنجم تا نهم پنج روز متوالی فروش صعودی داشته است و همچنین در روز بیستم تا بیست هشتم بازهم 5 روز متوالی فروش صعودی داشته است.
داده های آزمایشی را برای تست راه حلتان استفاده کنید. جواب باید 1 باشد.
INSERT INTO Sales
VALUES (1, 12, 60),
(1, 15, 70),
(1, 16, 80),
(1, 17, 83),
(1, 19, 86),
(1, 20, 90),
(1, 21, 90),
(2, 12, 80),
(2, 13, 70),
(2, 14, 70),
(2, 17, 50),
(2, 18, 60),
(2, 19, 70),
(2, 20, 80),
(2, 21, 0),
(3, 12, 70),
(3, 13, 60),
(3, 14, 50),
(3, 15, 60),
(3, 16, 60),
(3, 17, 65),
(3, 21, 65),
(4, 1, 5),
(4, 2, 6),
(4, 3, 6),
(4, 4, 7),
(4, 5, 8),
(5, 1, 1),
(5, 2, 2),
(5, 3, 3);
راه حل ها
اولین راه حل توسط آقای رضا یاراحمدی پیشنهاد شد. روشی که معرفی شد توسط ایشان سطر جاری را با 4 سطر بعدی (بر اساس نزدیک ترین روز) اتصال می داد و در صورتی که 5 مقدار به ترتیب از همدیگر بزرگتر بودند در خروجی اعلام می شد. و از آنجایی که ممکن بود فردی در بیش از 5 روز فروش صعودی داشته باشد یا اینکه در دو بازه ی زمانی جدا از هم 5 روز فروش صعودی داشته باشد از کلید واژه ی DISITNCT استفاده شده بود تا فروشنده های تکراری را حذف کند.
subquery های وابسته قطعا هزینه ی بالایی را به سیستم تحمیل می کرد و همچنین هزینه توسعه ی این روش بسیار بالا بود و به عبارتی قابل تعمیم به سختی بود. و برای مقادیر متغیر قابل استفاده نبود.
دومین روش توسط آقای صادقیان مطرح شد. ایده، ایده ی خوبی بود ولی متاسفانه مساله را به درستی حل نمیکرد و پشت سر هم بودن روزها در این راه حل در نظر گرفته نمی شد. ولی در کل تلاش قابل تحسینی بود.
و در انتها آخرین روشی که ارسال کردم کوتاه ترین روش بود. که اگر با این دیدگاه کلاسیک از همان ابتدا به مساله نگاه میشد این راه حل تولید میشد:
راه حل برنده
/*Msalim 4: 238 Chars*/
SELECT DISTINCT user_nbr
FROM Sales S
WHERE (SELECT COUNT(*)
FROM Sales D
WHERE S.user_nbr = user_nbr
AND S.day_nbr < day_nbr
AND S.value < value
AND NOT EXISTS
(SELECT *
FROM Sales
WHERE user_nbr = S.user_nbr
AND day_nbr > S.day_nbr AND day_nbr < D.day_nbr
AND value <= S.value)) >= 5;