المشكلة هي أنه من السهل للغاية كتابة تعليمات لا تعني ما تعتقده. على سبيل المثال ، قد يتحدى البرنامج تمامًا تفسير الكمبيوتر. الى جانب ذلك ،لا توجد طريقة حرفيًا لمعرفة ما إذا كان البرنامج سينتهي على الإطلاق دون تنفيذه. وهناك العديد والعديد من الطرق لإبطاء تنفيذ البرنامج كثيرًا. أعني ... بطيء حقًا . أبطئها حتى تستغرق حياتك كلها أو أكثر. يحدث هذا غالبًا مع البرامج التي يكتبها أشخاص بدون تعليم الكمبيوتر ، أي علماء من مجالات أخرى. وظيفتي هي إصلاح مثل هذه البرامج.
لا يفهم الناس أن علوم الكمبيوتر تعلمك نظرية الحساب ، وتعقيد الخوارزميات ، والقابلية للحساب (أي ، هل يمكننا حقًا حساب شيء ما؟ في كثير من الأحيان نعتبر أنه من المسلم به أننا نستطيع!) توفر علوم الكمبيوتر المعرفة والمنطق وأساليب التحليل للمساعدة في الكتابة رمز سيتم تنفيذه في أقل قدر من الوقت أو بأقل قدر من استخدام الموارد.
اسمحوا لي أن أريكم مثالاً على تحسين ضخم في نص بسيط واحد كتبه زميل لي.
نحن نتوسع كثيرًا في علم المناخ. نأخذ قراءات درجات الحرارة وهطول الأمطار من نموذج مناخ عالمي واسع النطاق ونقارنها بشبكة محلية دقيقة النطاق. لنفترض أن الشبكة العامة 50x25 والشبكة المحلية 1000x500. لكل خلية شبكة في الشبكة المحلية ، نريد معرفة أي خلية الشبكة في الشبكة العالمية تتوافق معها.
طريقة بسيطة لتمثيل المشكلة هي تقليل المسافة بين L [n] و G [n]. اتضح مثل هذا البحث:
L[i]:
G[j]:
L[i] G[j]
L[i] * G
يبدو بسيطا بما فيه الكفاية. ومع ذلك ، إذا نظرت عن كثب ، فإننا نقوم بالكثير من العمل الإضافي. انظر إلى الخوارزمية من حيث حجم المدخلات.
L[i]: # L
G[j]: # L x G
L[i] G[j] # L x G
d[i*j] # G L (L x G)
, # G L (L x G)يبدو الرمز مثل هذا:
obs.lon <- ncvar_get(nc.obs, 'lon')
obs.lat <- ncvar_get(nc.obs, 'lat')
n.lon <- length(obs.lon)
n.lat <- length(obs.lat)
obs.lats <- matrix(obs.lat, nrow=n.lon, ncol=n.lat, byrow=TRUE)
obs.lons <- matrix(obs.lon, nrow=n.lon, ncol=n.lat)
obs.time <- netcdf.calendar(nc.obs)
gcm.lon <- ncvar_get(nc.gcm, 'lon')-360
gcm.lat <- ncvar_get(nc.gcm, 'lat')
gcm.lats <- matrix(gcm.lat, ncol=length(gcm.lat), nrow=length(gcm.lon),
byrow=TRUE)
gcm.lons <- matrix(gcm.lon, ncol=length(gcm.lat), nrow=length(gcm.lon))
gcm.lons.lats <- cbind(c(gcm.lons), c(gcm.lats))
# Figure out which GCM grid boxes are associated with each fine-scale grid point
# Confine search to 10 deg. x 10 deg. neighbourhood
dxy <- 10
mdist <- function(x, y)
apply(abs(sweep(data.matrix(y), 2, data.matrix(x), '-')), 1, sum)
nn <- list()
for (i in seq_along(obs.lons)) {
if((i %% 500)==0) cat(i, '')
gcm.lims <- ((gcm.lons.lats[,1] >= (obs.lons[i]-dxy)) &
(gcm.lons.lats[,1] <= (obs.lons[i]+dxy))) &
((gcm.lons.lats[,2] >= (obs.lats[i]-dxy)) &
(gcm.lons.lats[,2] <= (obs.lats[i]+dxy)))
gcm.lims <- which(gcm.lims)
nn.min <- which.min(mdist(c(obs.lons[i], obs.lats[i]),
gcm.lons.lats[gcm.lims,]))
nn[[i]] <- gcm.lims[nn.min]
}
nn <- unlist(nn)يبدو وكأنه خوارزمية بسيطة. من "السهل" حساب المسافات ثم إيجاد الحد الأدنى. ولكن في مثل هذا التنفيذ ، مع نمو عدد الخلايا المحلية ، تزداد التكلفة الحسابية لدينا من خلال منتجها مع عدد الخلايا في الشبكة العالمية. تحتوي بيانات ANUSPLIN الكندية على 1،068 × 510 خلية (إجمالي 544،680). لنفترض أن GCM تحتوي على 50 × 25 خلية (إجمالي 1250). وبالتالي ، فإن تكلفة الدورة الداخلية في "بعض الوحدات الحسابية" هي:
حيث الأعضاء هي ثوابت مقابلة لتكلفة حساب المسافة بين نقطتين وإيجاد الحد الأدنى وإيجاد فهرس الصفيف. لا نهتم كثيرًا بالأعضاء الدائمين ، لأنهم لا يعتمدون على حجم المدخلات. لذلك يمكنك فقط جمعها وتقدير تكلفة الحساب ؛
لذلك ، بالنسبة لهذه المجموعة من المدخلات ، فإن التكلفة لدينا هي ...
680 مليون.
يبدو كثيرًا ... على الرغم من ، من يدري؟ أجهزة الكمبيوتر سريعة ، أليس كذلك؟ إذا قمنا بتنفيذ تطبيق ساذج ، فسيتم تشغيله في الواقع أسرع قليلاً من 1668 ثانية ، أي أقل بقليل من نصف ساعة.
> source('BCCA/naive.implementation.R')
500 1000 1500 2000 2500 3000 ... 543000 543500 544000 544500 [1] "Elapsed Time"
user system elapsed
1668.868 8.926 1681.728 لكن هل يجب تشغيل البرنامج لمدة 30 دقيقة؟ تلك هي المشكلة. نحن نقارن شبكتين ، كل منهما بها الكثير من الهياكل التي لم نستخدمها بأي شكل من الأشكال. على سبيل المثال ، خطوط الطول والعرض في كلا الشبكتين مرتبة بترتيب. لذلك ، للعثور على رقم ، لا تحتاج إلى المرور عبر المصفوفة بأكملها. يمكنك استخدام خوارزمية النصف - انظر إلى النقطة في المنتصف وحدد نصف المصفوفة الذي نريده. بعد ذلك ، سيأخذ البحث في المساحة بأكملها اللوغاريتم الأساسي الثاني لمساحة البحث بأكملها.
هيكل مهم آخر لم نستخدمه هو حقيقة أن خطوط العرض تذهب في الأبعاد، وخطوط الطول - في البعد ... وبالتالي ، بدلاً من إجراء العملية لأننا نستطيع فعل ذلك زمن. هذا تحسين ضخم .
كيف تبدو في الكود الكاذب؟
local[x]:
bisect_search(local[x], Global[x])
local[y]:
bisect_search(local[y], Global[y])
2d في الكود:
## Perform a binary search on the *sorted* vector v
## Return the array index of the element closest to x
find.nearest <- function(x, v) {
if (length(v) == 1) {
return(1)
}
if (length(v) == 2) {
return(which.min(abs(v - x)))
}
mid <- ceiling(length(v) / 2)
if (x == v[mid]) {
return(mid)
} else if (x < v[mid]) {
return(find.nearest(x, v[1:mid]))
}
else {
return((mid - 1) + find.nearest(x, v[mid:length(v)]))
}
}
regrid.one.dim <- function(coarse.points, fine.points) {
return(sapply(fine.points, find.nearest, coarse.points))
}
## Take a fine scale (e.g. ANUSPLINE) grid of latitudes and longitudes
## and find the indicies that correspond to a coarse scale (e.g. a GCM) grid
## Since the search is essentially a minimizing distance in 2 dimensions
## We can actually search independently in each dimensions separately (which
## is a huge optimization, making the run time x + y instead of x * y) and
## then reconstruct the indices to create a full grid
regrid.coarse.to.fine <- function(coarse.lats, coarse.lons, fine.lats, fine.lons) {
xi <- regrid.one.dim(gcm.lon, obs.lon)
yi <- regrid.one.dim(gcm.lat, obs.lat)
## Two dimensional grid of indices
xi <- matrix(xi, ncol=length(fine.lats), nrow=length(fine.lons), byrow=F)
yi <- matrix(yi, ncol=length(fine.lats), nrow=length(fine.lons), byrow=T)
return(list(xi=xi, yi=yi))
}تكلفة كل بحث نصف هو سجل حجم المدخلات. هذه المرة ، يتم تقسيم حجم الإدخال إلى مساحة X و Y ، لذلك سنستخدم و لـ Global و Local و X و Y.
التكلفة تصل إلى 553.076. حسنًا ، 553 ألف صوت أفضل بكثير من 680 مليونًا. كيف سيؤثر هذا على وقت التشغيل؟
> ptm <- proc.time(); rv <- regrid.coarse.to.fine(gcm.lat, gcm.lon, obs.lat, obs.lon); print('Elapsed Time'); print(proc.time() - ptm)[1] "Elapsed Time"
user system elapsed
0.117 0.000 0.117
> str(rv)
List of 2
$ xi: num [1:1068, 1:510] 15 15 15 15 15 15 15 15 15 15 ...
$ yi: num [1:1068, 1:510] 13 13 13 13 13 13 13 13 13 13 ...
> 0.117 ثانية. ما كان يستغرق نصف ساعة تقريبًا يستغرق الآن ما يزيد قليلاً عن عُشر ثانية.
> 1668.868 / .117
[1] 14263.83Soooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo، ولكن حتى أنا مندهش ومعجب كم هو تسريع. ما يقرب من 14 ألف مرة .
في السابق ، كان البرنامج النصي بطيئًا جدًا لدرجة أنه حفظ النتيجة على القرص للمراجعة اليدوية من قبل العلماء قبل المتابعة. الآن يتم حساب كل شيء في غمضة عين. نجري مثل هذه الحسابات مئات المرات ، حتى نوفر في النهاية أيامًا وحتى أسابيع من وقت الحوسبة. ونحصل على فرصة للتفاعل بشكل أفضل مع النظام ، بحيث يكون وقت عمل العلماء أكثر ربحية ... فهم لا يجلسون مكتوفي الأيدي ، في انتظار نهاية الحسابات. كل شيء جاهز في الحال.
يجب أن أؤكد أن هذه التحسينات الملحمية في الأداء لا تتطلب شراء أي أنظمة كمبيوتر كبيرة أو موازاة أو زيادة التعقيد ... في الواقع ، فإن كود الخوارزمية الأسرع هو أبسط وأكثر تنوعًا! تم تحقيق هذا النصر الكامل ببساطة من خلال القراءة المدروسة للشفرة والحصول على بعض المعرفة بالتعقيد الحسابي.