Bu durum, bir öğrencinin akademik disiplininin programlama konusundaki potansiyel yetkinliğinin iyi bir göstergesi olduğu yönünde sıkça yapılan varsayıma doğrudan karşıttır. Bu sonuç, bir ders uygun biçimde yapılandırılıp sunulduğunda, öğrenme yeteneği ya da disiplinler arası rekabet kaygıları nedeniyle farklı akademik disiplinlerden gelen öğrencileri ayırmaya gerek olmadığını göstermektedir.

Akademik performans açısından cinsiyetler arasında anlamlı bir fark bulunmamıştır. Gözlemlenebilen tek fark, kadınların akademik performanslarının erkeklere göre daha homojen görünmesidir.

Okulda geçirilen dönem sayısı ile akademik performans arasında bulunan korelasyonlar çok düşüktür. Bu durum açıkça göstermektedir ki uygun biçimde yapılandırılmış bir derste, üniversite deneyimine yeni başlayan öğrenciler ile akademik kariyerlerinde ilerlemiş olanlar arasında özel bir endişe duymak için bir neden yoktur. Hepsi hemen hemen aynı şekilde başarılı olmakta ya da başarısız olmaktadır.

Sonuçlar, gelecekteki programlama becerisinin en yaygın kullanılan yazılı testle (IBM'in Programming Aptitude Test'i) öngörülemediğini göstermektedir. Öneri, bu tür bir testin üniversite düzeyindeki kişilere uygulanmaması gerektiği yönündedir; çünkü sonuçlar güvenilir değildir.

Farklı disiplinlerden ve farklı akademik deneyim düzeylerinden gelen kişiler için ayrı ve rekabet eden dersler tasarlamak gerekli değildir; çünkü eşit olmayan yetenekler konusunda endişe duyulmasını gerektiren görünür bir durum yoktur. Ayrıca, üniversite düzeyindeki kişiler söz konusu olduğunda, programlama öğreniminde başarıyı normalde gözlemlenebilen dışsal kişisel özelliklere veya standartlaştırılmış yazılı testlere dayanarak güvenilir biçimde öngörmek de mümkün değildir.

Mayıs 1978'de alındı; Eylül 1978'de gözden geçirildi; Eylül 1979'da kabul edildi

Giriş

Kaynaklar

1. Bateman, C.R. Temel bir bilgisayar dersinde performansın öngörülmesi. Proc. of the Fifth Annual Meeting of the Amer. Inst. for Decision Sciences, Boston, Mass., 1973.
2. Newstead, P.R. Giriş düzeyi bir programlama dersinde not ve yetenek tahminleri. SIGCSE Bull. 7, 2 (Haziran 1975), s. 87–91.

Minimal Mükemmel Hash Fonksiyonlarının Basit Bir Şekilde Elde Edilmesi

Richard J. Cichelli
Software Consulting Services, Allentown, Pennsylvania

Aşağıdaki biçimde makineden bağımsız, minimal mükemmel hash fonksiyonlarının hesaplanması için bir yöntem sunulmaktadır:

hash değeri ← anahtar uzunluğu + anahtarın ilk karakterinin ilişkili değeri + anahtarın son karakterinin ilişkili değeri.

Bu tür fonksiyonlar, tanımlayıcı listelerinden oluşan minimal boyutlu tablolardan tek erişimle (single probe) veri elde edilmesine olanak tanır. Uygulama alanları arasında derleyicilerde ayrılmış sözcükler için tablo araması ve doğal dil işlemede yüksek frekanslı sözcüklerin filtrelenmesi bulunmaktadır. Pascal'ın ayrılmış sözcükleri, Pascal'ın ön tanımlı tanımlayıcıları, sık kullanılan İngilizce sözcükler ve ay kısaltmaları için fonksiyonlar örnek olarak sunulmaktadır.

Anahtar Sözcükler ve İfadeler: hashing, hashing yöntemleri, hash kodlama, doğrudan adresleme, sözlük araması, bilgi erişimi, sözcüksel analiz, tanımlayıcıdan adrese dönüşümler, mükemmel hash fonksiyonları, mükemmel hash kodlama, scatter storage, arama, Pascal, Pascal ayrılmış sözcükleri, backtracking

CR Kategorileri: 3.7, 3.74, 4.34, 5.25, 5.39

Giriş

Yakın zamanda yayımlanan bazı makalelerde [2, 3], statik tanımlayıcı listeleri (anahtarlar) için minimal mükemmel hash fonksiyonlarının hesaplanmasının genel olarak zor olduğu ileri sürülmüştür. [1] numaralı çalışmada Knuth da mükemmel hash fonksiyonlarının hesaplanmasındaki zorluğa dikkat çekmektedir. Burada Örnek No. 3'te kullanılan sözcük kümesi için böyle bir fonksiyonun aranmasının 10^43 olasılığın incelenmesini içerebileceğini tahmin etmektedir.

Bu makalede özetlenen yöntemi gerçekleştiren bir program, bu sözcükler için makineden bağımsız minimal mükemmel bir hash fonksiyonunu DEC PDP‑11/45 minibilgisayarında bir saniyeden kısa sürede bulmaktadır. Bu tür fonksiyonların başka örnekleri de gösterilmekte ve bunların hesaplanması için etkili bir yöntem açıklanmaktadır.

Algoritmam potansiyel olarak büyük uzaylarda üstel arama gerektirse de, bu uzayların akıllı bir şekilde aranmasına dayanmaktadır. Bu yöntemin birçok küme için birkaç saniye içinde çözümler bulduğu gösterilmiştir. Pascal'ın kırk ön tanımlı tanımlayıcısından otuz dokuzu için (Örnek No. 2), potansiyel arama uzayı 20^39 düğümden oluşmaktaydı. Fonksiyonun hesaplanması PDP‑11/45 üzerinde yedi dakika sürmüştür. Birçok kez kullanılacak arama tabloları için yöntem oldukça pratik olduğunu göstermiştir. Şimdiye kadar sonsuz derecede uzun süren bir aramayla karşılaşılmamıştır.

Hash Fonksiyonu Biçimi

Hash fonksiyonumun biçimi şöyledir:

Hash değeri ← anahtar uzunluğu + anahtarın ilk karakterinin ilişkili değeri + anahtarın son karakterinin ilişkili değeri.

Yukarıdaki biçimdeki hash fonksiyonlarının avantajı, basit, verimli ve makineden (yani karakter gösteriminden) bağımsız olmalarıdır. Ayrıca herhangi bir sözcüksel tarama sürecinin, tanımlayıcı tarama mantığının bir yan ürünü olarak, tanımlayıcı uzunluğunu ve ilk ve son karakterlerin değerlerini zaten elde etmiş olması da muhtemeldir.

Bu biçimdeki fonksiyonların iki dezavantajı vardır:

1. İki anahtarın aynı uzunluğu ve aynı ilk ve son karakterleri paylaşmaması gerekir.
2. Yaklaşık 45 öğeden fazla içeren listeler için alt listelere bölme gerekebilir. (Bu durum, fonksiyonların ürettiği hash değerlerinin sınırlı aralığından kaynaklanır.)

Örnek No. 1: Pascal'ın Ayrılmış Sözcükleri

Pascal'ın 36 ayrılmış sözcüğü için aşağıdaki liste her harf için ilişkili değeri tanımlar:

A = 11, B = 15, C = 1, D = 0, E = 0, F = 15, G = 3, H = 15, I = 13,
J = 0, K = 0, L = 15, M = 15, N = 13, O = 0, P = 15, Q = 0, R = 14,
S = 6, T = 6, U = 14, V = 10, W = 6, X = 0, Y = 13, Z = 0.

(Arama yordamları için bu değerler, harflerle indekslenen bir tamsayı dizisinde saklanır. Not: ilişkili değerlerin benzersiz olması gerekmez.)

Hash değerleri 2 ile 37 arasında değişen karşılık gelen hash tablosu şu şekildedir:

DO, END, ELSE, CASE, DOWNTO, GOTO, TO, OTHERWISE, TYPE, WHILE, CONST, DIV, AND, SET, OR, OF, MOD, FILE, RECORD, PACKED, NOT, THEN, PROCEDURE, WITH, REPEAT, VAR, IN, ARRAY, IF, NIL, FOR, BEGIN, UNTIL, LABEL, FUNCTION, PROGRAM.

Örnek olarak "CASE" için hesaplamayı ele alalım:

(1 ← "C") + (0 ← "E") + (4 ← length("CASE")) = 5

Arama Listesinin Sıralanması

Her harf için ilişkili değerler aşağıdaki yordam ile hesaplanır:

1. Tanımlayıcı listesini sırala.
2. Backtracking kullanarak çözüm ara.

Sıralama işlemi iki aşamalıdır.

Önce, anahtarları her bir anahtarın ilk ve son harfinin listedeki görülme sıklıklarının toplamına göre sırala. Örneğin "E", Pascal ayrılmış sözcük listesinde ilk veya son harf olarak dokuz kez görülür. En sık görülen harftir ve bu nedenle "ELSE" arama listesindeki ilk sözcüktür. "D" bir sonraki en sık görülen harftir ve bu nedenle "END" ikinci sıradadır.

Sözcükler karakter görülme sıklıklarına göre sıralandıktan sonra, hash değeri daha önceki sözcükler tarafından zaten belirlenmiş ilişkili karakter değerleri atanarak belirlenebilen herhangi bir sözcüğün sırada bir sonraya yerleştirilmesi sağlanacak şekilde listenin sırasını değiştir.

Örneğin arama sırasında "END" sözcüğünün yerleştirilmesinden sonra "D" için bir değer atanmış olacaktır ve "OTHERWISE" yerleştirildikten sonra "O" için bir değer atanmış olacaktır. Bu sıralama işlemi, kaçınılmaz hash değeri çakışmalarının arama sırasında mümkün olduğunca erken gerçekleşmesini sağlar; böylece arama ağacı budanır ve hesaplama hızlanır.

Pascal'ın ayrılmış sözcükleri için tamamen sıralanmış arama listesi şöyledir:

ELSE, END, OTHERWISE, DO, DOWNTO, TYPE, TO, FILE, OF, THEN, NOT, FUNCTION, RECORD, REPEAT, OR, FOR, PROCEDURE, PACKED, WHILE, CASE, CONST, DIV, VAR, AND, MOD, PROGRAM, NIL, LABEL, SET, IN, IF, GOTO, BEGIN, UNTIL, ARRAY, WITH.

Backtracking Arama Yöntemi

Backtracking arama yöntemi, anahtar sözcük listesinin tüm üyelerine benzersiz referans verilmesine izin verecek ilişkili değerler kümesini bulmaya çalışır.

Yöntem şu şekilde çalışır:

• Tanımlayıcının hem ilk hem de son harfinin zaten ilişkili değerleri varsa, sözcüğü dene.
• İlk veya son harften biri ilişkili bir değere sahipse, atanmamış karakterin ilişkili değerini sıfırdan izin verilen maksimum değere kadar değiştirerek her olasılığı dene.
• Her iki harf de ilişkilendirilmemişse, önce birincisini sonra ikincisini değiştirerek tüm olası kombinasyonları dene.

İlk ve son harflerin aynı olduğu durumlar için bir istisna testi gereklidir.

Her "deneme", verilen hash değerinin daha önce atanıp atanmadığını test eder; atanmadıysa değeri ayırır ve harfleri atar. Tüm tanımlayıcılar seçilmişse çözümü yazdırır ve durur. Aksi halde bir sonraki sözcüğü yerleştirmek için arama yordamını özyineli olarak çağırır. Deneme başarısız olursa sözcük backtracking ile geri alınır.

Bu tür fonksiyonların hesaplanması için gereken arama süresi şu etkenlerle ilişkilidir:

• Yerleştirilecek tanımlayıcı sayısı
• Bir karakterle ilişkilendirilebilecek maksimum değer
• Ortaya çıkan hash tablosunun yoğunluğu

Tablo yoğunluğu bir olduğunda (yani minimal mükemmel hash) ve maksimum ilişkili değer, farklı ilk ve son harf görülme sayısına eşit olduğunda (Pascal ayrılmış sözcükleri için 21), yöntem basit bir Pascal uygulaması kullanılarak DEC PDP‑11/45 üzerinde yaklaşık yedi saniyede çözüm bulur.

İkinci sıralama uygulanmadığında arama 5,5 saat sürmüştür. Maksimum ilişkili değer yukarıdaki listede olduğu gibi 15 ile sınırlandırıldığında arama yaklaşık 40 dakika sürmektedir. (Maksimum değer 14 olduğunda çözüm yoktur.)

Yukarıdaki hash fonksiyonunun bir Pascal çapraz başvuru programına eklenmesi, büyük programların işlenmesinde toplam çalışma süresinde yüzde 10 azalma sağlamıştır. Yöntem, ayrılmış sözcükleri çapraz başvuru dışında bırakmak için kullanılan iyi kodlanmış bir ikili aramanın yerini almıştır.

Örnek No. 2: Pascal'ın Ön Tanımlı Tanımlayıcıları

İlişkili değerler:

A = 15, B = 9, C = 11, D = 19, E = 5, F = 3, G = 0, H = 0, I = 3,
J = 0, K = 16, L = 13, M = 1, N = 19, O = 0, P = 18, Q = 0, R = 0,
S = 15, T = 0, U = 17, V = 0, W = 10, X = 0, Y = 0, Z = 0.

Tanımlayıcılar:

GET, TEXT, RESET, OUTPUT, MAXINT, INPUT, TRUE, INTEGER, EOF, REWRITE, FALSE, CHR, CHAR, TRUNC, REAL, SQR, SQRT, WRITE, PUT, ORD, READ, ROUND, READLN, EXP, PAGE, EOLN, COS, SUCC, DISPOSE, NEW, ABS, LN, BOOLEAN, WRITELN, SIN, PACK, UNPACK, ARCTAN, PRED.

Bu fonksiyonun hesaplanması yaklaşık yedi dakika sürmüştür. Not: Ön tanımlı tanımlayıcı "ODD", "ORD" ile çakıştığı için listeye dahil edilmemiştir.

Örnek No. 3: Sık Kullanılan İngilizce Sözcükler

İlişkili değerler:

A = 3, B = 15, C = 0, D = 7, E = 0, F = 15, G = 0, H = 10, I = 0,
J = 0, K = 0, L = 0, M = 12, N = 13, O = 7, P = 0, Q = 0, R = 12,
S = 6, T = 0, U = 15, V = 0, W = 14, X = 0, Y = 9, Z = 0.

Sözcük listesi:

I, it, the, that, at, are, a, is, to, this, as, he, and, have, in, not, be, but, his, had, or, on, was, of, her, by, you, with, which, for, from.

Arama süresi bir saniyeden daha azdır.

Örnek No. 4: Ay Kısaltmaları

Bu örnekte fonksiyon biraz değiştirilmiştir:

Hash değeri ← anahtarın ikinci karakterinin ilişkili değeri + anahtarın üçüncü karakterinin ilişkili değeri.

İlişkili değerler:

A = 4, B = 5, C = 2, D = 0, E = 0, F = 0, G = 3, H = 0, I = 0,
J = 0, K = 0, L = 6, M = 0, N = 0, O = 5, P = 1, Q = 0, R = 6,
S = 0, T = 6, U = 0, V = 6, W = 0, X = 0, Y = 5, Z = 0.

Bu biçim "JAN" ve "JUN" arasındaki çakışmayı önler ve sabit anahtar uzunluğunu dikkate alır.

Arama süresi yine bir saniyenin oldukça altındadır.

Not: Burada sunulan yöntem, [3]'te açıklanan yöntemlerle uygulanabilir olduğu söylenen kümelerden dört kat daha büyük kümelere uygulanabilir.

Ders

Bu makalenin bir sonucu yoktur, ancak bir dersi vardır. Günümüzün son derece başarılı satranç programları neslinin prototipi olan Technology Chess Program'ın yazarı, ünlü satranç programcısı J. Gillogly'nin sözleriyle:

"Başka her şey başarısız olduğunda, kaba kuvveti dene."

Kaynaklar

1. Knuth, D.E. The Art of Computer Programming, Cilt 3: Sorting and Searching. Addison‑Wesley, Reading, Mass., 1973, s. 506–507.
2. Sheil, B.A. Median split trees: Sık görülen anahtarlar için hızlı bir arama tekniği. Comm. ACM 21, 11 (Kasım 1978), 947–958.
3. Sprugnoli, R. Perfect hashing functions: Statik kümeler için tek erişimli bir geri getirme yöntemi. Comm. ACM 20, 11 (Kasım 1977), 841–850.

Mayıs 1979'da alındı; Ekim 1979'da gözden geçirildi ve kabul edildi