演算法實現類
Ⅰ DES演算法實現
完成一個DES 演算法的 詳細設計 ,內容包括：
DES（Data Encryption Standard）是一種用於電子數據加密的對稱密鑰塊加密演算法 .它以64位為分組長度，64位一組的明文作為演算法的輸入，通過一系列復雜的操作，輸出同樣64位長度的密文。DES 同樣採用64位密鑰，但由於每8位中的最後1位用於奇偶校驗，實際有效密鑰長度為56位。密鑰可以是任意的56位的數，且可隨時改變。
DES 使用加密密鑰定義變換過程，因此演算法認為只有持有加密所用的密鑰的用戶才能解密密文。DES的兩個重要的安全特性是混淆和擴散。其中 混淆 是指通過密碼演算法使明文和密文以及密鑰的關系非常復雜，無法從數學上描述或者統計。 擴散 是指明文和密鑰中的每一位信息的變動，都會影響到密文中許多位信息的變動，從而隱藏統計上的特性，增加密碼的安全。
DES演算法的基本過程是換位和置換。如圖，有16個相同的處理階段，稱為輪。還有一個初始和最終的排列，稱為 IP 和 FP，它們是反向的 (IP 取消 FP 的作用，反之亦然)。
在主輪之前，塊被分成兩個32位的一半和交替處理；這種縱橫交錯的方案被稱為Feistel 方法。Feistel 結構確保了解密和加密是非常相似的過程——唯一的區別是在解密時子鍵的應用順序是相反的。其餘的演算法是相同的。這大大簡化了實現，特別是在硬體中，因為不需要單獨的加密和解密演算法。
符號表示異或（XOR）操作。Feistel 函數將半塊和一些鍵合在一起。然後，將Feistel 函數的輸出與塊的另一半組合在一起，在下一輪之前交換這一半。在最後一輪之後，兩隊交換了位置；這是 Feistel 結構的一個特性，使加密和解密過程類似。
IP 置換表指定64位塊上的輸入排列。其含義如下：輸出的第一個比特來自輸入的第58位;第二個位來自第50位，以此類推，最後一個位來自第7位輸入。
最後的排列是初始排列的倒數。
展開函數被解釋為初始排列和最終排列。注意，輸入的一些位在輸出時是重復的;輸入的第5位在輸出的第6位和第8位中都是重復的。因此，32位半塊被擴展到48位。
P排列打亂了32位半塊的位元。
表的「左」和「右」部分顯示了來自輸入鍵的哪些位構成了鍵調度狀態的左和右部分。輸入的64位中只有56位被選中；剩下的8（8、16、24、32、40、48、56、64）被指定作為奇偶校驗位使用。
這個排列從56位鍵調度狀態為每輪選擇48位的子鍵。
這個表列出了DES中使用的8個S-box，每個S-box用4位的輸出替換6位的輸入。給定一個6位輸入，通過使用外部的兩個位選擇行，以及使用內部的四個位選擇列，就可以找到4位輸出。例如，一個輸入「011011」有外部位「01」和內部位「1101」。第一行為「00」，第一列為「0000」，S-box S5對應的輸出為「1001」(=9)，即第二行第14列的值。
DES演算法的基本流程圖如下：
DES演算法是典型的對稱加密演算法，在輸入64比特明文數據後，通過輸入64比特密鑰和演算法的一系列加密步驟後，可以得到同樣為64比特的密文數據。反之，我們通過已知的密鑰，可以將密文數據轉換回明文。 我們將演算法分為了三大塊：IP置換、16次T迭代和IP逆置換 ，加密和解密過程分別如下：
實驗的設計模式是自頂向下的結構，用C語言去分別是先各個函數的功能，最後通過主函數將所有函數進行整合，讓演算法更加清晰客觀。
通過IP置換表，根據表中所示下標，找到相應位置進行置換。
對於16次 迭代，我們先將傳入的經過 IP 混淆過的64位明文的左右兩部分，分別為32位的 和32位的 。之後我們將 和 進行交換，得到作為IP逆置換的輸入：
，
子密鑰的生成，經歷下面一系列步驟：首先對於64位密鑰，進行置換選擇，因為將用戶輸入的64 位經歷壓縮變成了56位，所以我們將左面和右面的各28位進行循環位移。左右兩部分分別按下列規則做循環移位：當 ，循環左移1位；其餘情況循環左移2位。最後將得到的新的左右兩部分進行連接得到56位密鑰。
對半塊的 Feistel 操作分為以下五步：
如上二圖表明，在給出正確的密碼後，可以得到對應的明文。
若密碼錯誤，將解碼出錯誤答案。
【1】 Data Encryption Standard
【2】 DES演算法的詳細設計（簡單實現）
【3】 深入理解並實現DES演算法
【4】 DES演算法原理完整版
【5】 安全體系（一）—— DES演算法詳解
Ⅱ 自定義數組類與演算法實現
// MyArray.h
#ifndef _MYARRAY_H_
#define _MYARRAY_H_
#include <cassert>
template<class T>
class MyArray
{
private:
T* list;
int size;
public:
MyArray (int sz = 50);
MyArray (const MyArray<T>&a); // 復制構造函數
~MyArray();
MyArray<T>& operator = (const MyArray<T>&rhs);
T & operator [] (int i);
const T & operator [] (int i) const;
operator T* ();
operator const T * () const;
int getSize () const;
void resize (int sz);
};
template<class T>
MyArray<T>::MyArray(int sz /* = 50 */)
{
assert(sz);
size = sz;
list = new T[size];
}
template<class T>
MyArray<T>::~MyArray()
{
delete[] list;
}
template<class T>
MyArray<T>::MyArray(const MyArray<T>& rhs) // 復制構造函數, 實現 深復制
{
size = rhs.size;
list = new T[size];
for(int i = 0; i < size; ++i)
list[i] = rhs.list[i];
}
template<class T>
MyArray<T>& MyArray<T>::operator = (const MyArray<T>&rhs) // 重載 =
{
if(this != &rhs)
if(size != rhs.size)
{
delete[] list;
size = rhs.size;
list = new T[size];
for(int i = 0; i < size; ++i)
list[i] = rhs.list[i];
}
return *this;
}
template<class T>
const T& MyArray<T>::operator [] (int i) const
{
assert(i >= 0 && i < size);
return list[i];
}
template<class T>
T& MyArray<T>::operator [] (int i)
{
assert(i >= 0 && i < size);
return list[i];
}
template<class T>
MyArray<T>::operator T *() // 為什麼不能定義為 T* MyArray<T>::operator T*()?
{
return list;
}
template<class T>
MyArray<T>::operator const T *() const // 為什麼 const 一定要放在最後?
{
return list;
}
template<class T>
int MyArray<T>::getSize () const
{
return size;
}
template<class T>
void MyArray<T>::resize (int sz)
{
assert(sz);
if(size != sz)
{
T* newList = new T[sz];
int n = size >sz ? sz : size;
size = sz;
for(int i = 0; i < n; ++i)
newList[i] = list[i];
delete[] list;
list = newList;
}
}
#endif // _MYARRAY_H_
示例代碼: MyArray 類的應用(動態建立素數表, 並驗證素數)
#include <iostream>
#include <iomanip>
#include "MyArray.h"
int main()
{
MyArray<int> a(10);
int count = 0;
int n;
cin>>n;
for (int i = 2; i < n;++i)
{
bool isPrime = true;
int t = sqrt ((double)i);
for (int j = 0; j < count; ++j)
{
if(i % a[j] == 0)
{
isPrime = false;
break;
}
if(t > a[j])
break;
}
if(isPrime)
{
if(count == a.getSize())
a.resize(count * 2);
a[count++] = i;
cout<<setw(8)<<a[count - 1];
}
}
for(int i = 0; i < count; ++i)
cout<<setw(8)<<a[i];
cout<<endl;
return 0;
}
Ⅲ 急需C++實現的Apriori演算法代碼
用C++ 實現的 可以 到http://download.csdn.net/down/188143/chanjuanzz下載 不過要注冊扣積分的
演算法實現
（一）核心類
Apriori演算法的核心實現類為AprioriAlgorithm，實現的java代碼如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
/**
* <B>關聯規則挖掘：Apriori演算法</B>
*
* <P>該演算法基本上按照Apriori演算法的基本思想來實現的。
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class AprioriAlgorithm {
private Map<Integer, Set<String>> txDatabase; // 事務資料庫
private Float minSup; // 最小支持度
private Float minConf; // 最小置信度
private Integer txDatabaseCount; // 事務資料庫中的事務數
private Map<Integer, Set<Set<String>>> freqItemSet; // 頻繁項集集合
private Map<Set<String>, Set<Set<String>>> assiciationRules; // 頻繁關聯規則集合
public AprioriAlgorithm(
Map<Integer, Set<String>> txDatabase,
Float minSup,
Float minConf) {
this.txDatabase = txDatabase;
this.minSup = minSup;
this.minConf = minConf;
this.txDatabaseCount = this.txDatabase.size();
freqItemSet = new TreeMap<Integer, Set<Set<String>>>();
assiciationRules = new HashMap<Set<String>, Set<Set<String>>>();
}
/**
* 掃描事務資料庫，計算頻繁1-項集
* @return
*/
public Map<Set<String>, Float> getFreq1ItemSet() {
Map<Set<String>, Float> freq1ItemSetMap = new HashMap<Set<String>, Float>();
Map<Set<String>, Integer> candFreq1ItemSet = this.getCandFreq1ItemSet();
Iterator<Map.Entry<Set<String>, Integer>> it = candFreq1ItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Set<String>, Integer> entry = it.next();
// 計算支持度
Float supported = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supported>=minSup) {
freq1ItemSetMap.put(entry.getKey(), supported);
}
}
return freq1ItemSetMap;
}
/**
* 計算候選頻繁1-項集
* @return
*/
public Map<Set<String>, Integer> getCandFreq1ItemSet() {
Map<Set<String>, Integer> candFreq1ItemSetMap = new HashMap<Set<String>, Integer>();
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 統計支持數，生成候選頻繁1-項集
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Set<String> itemSet = entry.getValue();
for(String item : itemSet) {
Set<String> key = new HashSet<String>();
key.add(item.trim());
if(!candFreq1ItemSetMap.containsKey(key)) {
Integer value = 1;
candFreq1ItemSetMap.put(key, value);
}
else {
Integer value = 1+candFreq1ItemSetMap.get(key);
candFreq1ItemSetMap.put(key, value);
}
}
}
return candFreq1ItemSetMap;
}
/**
* 根據頻繁(k-1)-項集計算候選頻繁k-項集
*
* @param m 其中m=k-1
* @param freqMItemSet 頻繁(k-1)-項集
* @return
*/
public Set<Set<String>> aprioriGen(int m, Set<Set<String>> freqMItemSet) {
Set<Set<String>> candFreqKItemSet = new HashSet<Set<String>>();
Iterator<Set<String>> it = freqMItemSet.iterator();
Set<String> originalItemSet = null;
while(it.hasNext()) {
originalItemSet = it.next();
Iterator<Set<String>> itr = this.getIterator(originalItemSet, freqMItemSet);
while(itr.hasNext()) {
Set<String> identicalSet = new HashSet<String>(); // 兩個項集相同元素的集合(集合的交運算)
identicalSet.addAll(originalItemSet);
Set<String> set = itr.next();
identicalSet.retainAll(set); // identicalSet中剩下的元素是identicalSet與set集合中公有的元素
if(identicalSet.size() == m-1) { // (k-1)-項集中k-2個相同
Set<String> differentSet = new HashSet<String>(); // 兩個項集不同元素的集合(集合的差運算)
differentSet.addAll(originalItemSet);
differentSet.removeAll(set); // 因為有k-2個相同，則differentSet中一定剩下一個元素，即differentSet大小為1
differentSet.addAll(set); // 構造候選k-項集的一個元素(set大小為k-1,differentSet大小為k)
candFreqKItemSet.add(differentSet); // 加入候選k-項集集合
}
}
}
return candFreqKItemSet;
}
/**
* 根據一個頻繁k-項集的元素(集合)，獲取到頻繁k-項集的從該元素開始的迭代器實例
* @param itemSet
* @param freqKItemSet 頻繁k-項集
* @return
*/
private Iterator<Set<String>> getIterator(Set<String> itemSet, Set<Set<String>> freqKItemSet) {
Iterator<Set<String>> it = freqKItemSet.iterator();
while(it.hasNext()) {
if(itemSet.equals(it.next())) {
break;
}
}
return it;
}
/**
* 根據頻繁(k-1)-項集，調用aprioriGen方法，計算頻繁k-項集
*
* @param k
* @param freqMItemSet 頻繁(k-1)-項集
* @return
*/
public Map<Set<String>, Float> getFreqKItemSet(int k, Set<Set<String>> freqMItemSet) {
Map<Set<String>, Integer> candFreqKItemSetMap = new HashMap<Set<String>, Integer>();
// 調用aprioriGen方法，得到候選頻繁k-項集
Set<Set<String>> candFreqKItemSet = this.aprioriGen(k-1, freqMItemSet);
// 掃描事務資料庫
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 統計支持數
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Iterator<Set<String>> kit = candFreqKItemSet.iterator();
while(kit.hasNext()) {
Set<String> kSet = kit.next();
Set<String> set = new HashSet<String>();
set.addAll(kSet);
set.removeAll(entry.getValue()); // 候選頻繁k-項集與事務資料庫中元素做差元算
if(set.isEmpty()) { // 如果拷貝set為空，支持數加1
if(candFreqKItemSetMap.get(kSet) == null) {
Integer value = 1;
candFreqKItemSetMap.put(kSet, value);
}
else {
Integer value = 1+candFreqKItemSetMap.get(kSet);
candFreqKItemSetMap.put(kSet, value);
}
}
}
}
// 計算支持度，生成頻繁k-項集，並返回
return support(candFreqKItemSetMap);
}
/**
* 根據候選頻繁k-項集，得到頻繁k-項集
*
* @param candFreqKItemSetMap 候選k項集(包含支持計數)
*/
public Map<Set<String>, Float> support(Map<Set<String>, Integer> candFreqKItemSetMap) {
Map<Set<String>, Float> freqKItemSetMap = new HashMap<Set<String>, Float>();
Iterator<Map.Entry<Set<String>, Integer>> it = candFreqKItemSetMap.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Set<String>, Integer> entry = it.next();
// 計算支持度
Float supportRate = new Float(entry.getValue().toString())/new Float(txDatabaseCount);
if(supportRate<minSup) { // 如果不滿足最小支持度，刪除
it.remove();
}
else {
freqKItemSetMap.put(entry.getKey(), supportRate);
}
}
return freqKItemSetMap;
}
/**
* 挖掘全部頻繁項集
*/
public void mineFreqItemSet() {
// 計算頻繁1-項集
Set<Set<String>> freqKItemSet = this.getFreq1ItemSet().keySet();
freqItemSet.put(1, freqKItemSet);
// 計算頻繁k-項集(k>1)
int k = 2;
while(true) {
Map<Set<String>, Float> freqKItemSetMap = this.getFreqKItemSet(k, freqKItemSet);
if(!freqKItemSetMap.isEmpty()) {
this.freqItemSet.put(k, freqKItemSetMap.keySet());
freqKItemSet = freqKItemSetMap.keySet();
}
else {
break;
}
k++;
}
}
/**
* <P>挖掘頻繁關聯規則
* <P>首先挖掘出全部的頻繁項集，在此基礎上挖掘頻繁關聯規則
*/
public void mineAssociationRules() {
freqItemSet.remove(1); // 刪除頻繁1-項集
Iterator<Map.Entry<Integer, Set<Set<String>>>> it = freqItemSet.entrySet().iterator();
while(it.hasNext()) {
Map.Entry<Integer, Set<Set<String>>> entry = it.next();
for(Set<String> itemSet : entry.getValue()) {
// 對每個頻繁項集進行關聯規則的挖掘
mine(itemSet);
}
}
}
/**
* 對從頻繁項集集合freqItemSet中每迭代出一個頻繁項集元素，執行一次關聯規則的挖掘
* @param itemSet 頻繁項集集合freqItemSet中的一個頻繁項集元素
*/
public void mine(Set<String> itemSet) {
int n = itemSet.size()/2; // 根據集合的對稱性，只需要得到一半的真子集
for(int i=1; i<=n; i++) {
// 得到頻繁項集元素itemSet的作為條件的真子集集合
Set<Set<String>> properSubset = ProperSubsetCombination.getProperSubset(i, itemSet);
// 對條件的真子集集合中的每個條件項集，獲取到對應的結論項集，從而進一步挖掘頻繁關聯規則
for(Set<String> conditionSet : properSubset) {
Set<String> conclusionSet = new HashSet<String>();
conclusionSet.addAll(itemSet);
conclusionSet.removeAll(conditionSet); // 刪除條件中存在的頻繁項
confide(conditionSet, conclusionSet); // 調用計算置信度的方法，並且挖掘出頻繁關聯規則
}
}
}
/**
* 對得到的一個條件項集和對應的結論項集，計算該關聯規則的支持計數，從而根據置信度判斷是否是頻繁關聯規則
* @param conditionSet 條件頻繁項集
* @param conclusionSet 結論頻繁項集
*/
public void confide(Set<String> conditionSet, Set<String> conclusionSet) {
// 掃描事務資料庫
Iterator<Map.Entry<Integer, Set<String>>> it = txDatabase.entrySet().iterator();
// 統計關聯規則支持計數
int conditionToConclusionCnt = 0; // 關聯規則(條件項集推出結論項集)計數
int conclusionToConditionCnt = 0; // 關聯規則(結論項集推出條件項集)計數
int supCnt = 0; // 關聯規則支持計數
while(it.hasNext()) {
Map.Entry<Integer, Set<String>> entry = it.next();
Set<String> txSet = entry.getValue();
Set<String> set1 = new HashSet<String>();
Set<String> set2 = new HashSet<String>();
set1.addAll(conditionSet);
set1.removeAll(txSet); // 集合差運算：set-txSet
if(set1.isEmpty()) { // 如果set為空，說明事務資料庫中包含條件頻繁項conditionSet
// 計數
conditionToConclusionCnt++;
}
set2.addAll(conclusionSet);
set2.removeAll(txSet); // 集合差運算：set-txSet
if(set2.isEmpty()) { // 如果set為空，說明事務資料庫中包含結論頻繁項conclusionSet
// 計數
conclusionToConditionCnt++;
}
if(set1.isEmpty() && set2.isEmpty()) {
supCnt++;
}
}
// 計算置信度
Float conditionToConclusionConf = new Float(supCnt)/new Float(conditionToConclusionCnt);
if(conditionToConclusionConf>=minConf) {
if(assiciationRules.get(conditionSet) == null) { // 如果不存在以該條件頻繁項集為條件的關聯規則
Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
conclusionSetSet.add(conclusionSet);
assiciationRules.put(conditionSet, conclusionSetSet);
}
else {
assiciationRules.get(conditionSet).add(conclusionSet);
}
}
Float conclusionToConditionConf = new Float(supCnt)/new Float(conclusionToConditionCnt);
if(conclusionToConditionConf>=minConf) {
if(assiciationRules.get(conclusionSet) == null) { // 如果不存在以該結論頻繁項集為條件的關聯規則
Set<Set<String>> conclusionSetSet = new HashSet<Set<String>>();
conclusionSetSet.add(conditionSet);
assiciationRules.put(conclusionSet, conclusionSetSet);
}
else {
assiciationRules.get(conclusionSet).add(conditionSet);
}
}
}
/**
* 經過挖掘得到的頻繁項集Map
*
* @return 挖掘得到的頻繁項集集合
*/
public Map<Integer, Set<Set<String>>> getFreqItemSet() {
return freqItemSet;
}
/**
* 獲取挖掘到的全部的頻繁關聯規則的集合
* @return 頻繁關聯規則集合
*/
public Map<Set<String>, Set<Set<String>>> getAssiciationRules() {
return assiciationRules;
}
}
（二）輔助類
ProperSubsetCombination類是一個輔助類，在挖掘頻繁關聯規則的過程中，用於生成一個頻繁項集元素的非空真子集，實現代碼如下：
package org.shirdrn.datamining.association;
import java.util.BitSet;
import java.util.HashSet;
import java.util.Set;
/**
* <B>求頻繁項集元素(集合)的非空真子集集合</B>
* <P>從一個集合（大小為n）中取出m(m屬於2~n/2的閉區間)個元素的組合實現類，獲取非空真子集的集合
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class ProperSubsetCombination {
private static String[] array;
private static BitSet startBitSet; // 比特集合起始狀態
private static BitSet endBitSet; // 比特集合終止狀態，用來控制循環
private static Set<Set<String>> properSubset; // 真子集集合
/**
* 計算得到一個集合的非空真子集集合
*
* @param n 真子集的大小
* @param itemSet 一個頻繁項集元素
* @return 非空真子集集合
*/
public static Set<Set<String>> getProperSubset(int n, Set<String> itemSet) {
String[] array = new String[itemSet.size()];
ProperSubsetCombination.array = itemSet.toArray(array);
properSubset = new HashSet<Set<String>>();
startBitSet = new BitSet();
endBitSet = new BitSet();
// 初始化startBitSet，左側占滿1
for (int i=0; i<n; i++) {
startBitSet.set(i, true);
}
// 初始化endBit，右側占滿1
for (int i=array.length-1; i>=array.length-n; i--) {
endBitSet.set(i, true);
}
// 根據起始startBitSet，將一個組合加入到真子集集合中
get(startBitSet);
while(!startBitSet.equals(endBitSet)) {
int zeroCount = 0; // 統計遇到10後，左邊0的個數
int oneCount = 0; // 統計遇到10後，左邊1的個數
int pos = 0; // 記錄當前遇到10的索引位置
// 遍歷startBitSet來確定10出現的位置
for (int i=0; i<array.length; i++) {
if (!startBitSet.get(i)) {
zeroCount++;
}
if (startBitSet.get(i) && !startBitSet.get(i+1)) {
pos = i;
oneCount = i - zeroCount;
// 將10變為01
startBitSet.set(i, false);
startBitSet.set(i+1, true);
break;
}
}
// 將遇到10後，左側的1全部移動到最左側
int counter = Math.min(zeroCount, oneCount);
int startIndex = 0;
int endIndex = 0;
if(pos>1 && counter>0) {
pos--;
endIndex = pos;
for (int i=0; i<counter; i++) {
startBitSet.set(startIndex, true);
startBitSet.set(endIndex, false);
startIndex = i+1;
pos--;
if(pos>0) {
endIndex = pos;
}
}
}
get(startBitSet);
}
return properSubset;
}
/**
* 根據一次移位操作得到的startBitSet，得到一個真子集
* @param bitSet
*/
private static void get(BitSet bitSet) {
Set<String> set = new HashSet<String>();
for(int i=0; i<array.length; i++) {
if(bitSet.get(i)) {
set.add(array[i]);
}
}
properSubset.add(set);
}
}
測試用例
對上述Apriori演算法的實現進行了簡單的測試，測試用例如下所示：
package org.shirdrn.datamining.association;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
import org.shirdrn.datamining.association.AprioriAlgorithm;
import junit.framework.TestCase;
/**
* <B>Apriori演算法測試類</B>
*
* @author shirdrn
* @date 2009/07/22 22:56:23
* @msn shirdrn#hotmail.com(#→@)
* @qq 187071722
*/
public class TestAprioriAlgorithm extends TestCase {
private AprioriAlgorithm apriori;
private Map<Integer, Set<String>> txDatabase;
private Float minSup = new Float("0.50");
private Float minConf = new Float("0.70");
@Override
protected void setUp() throws Exception {
create(); // 構造事務資料庫
apriori = new AprioriAlgorithm(txDatabase, minSup, minConf);
}
/**
* 構造模擬事務資料庫txDatabase
*/
public void create() {
txDatabase = new HashMap<Integer, Set<String>>();
Set<String> set1 = new TreeSet<String>();
set1.add("A");
set1.add("B");
set1.add("C");
set1.add("E");
txDatabase.put(1, set1);
Set<String> set2 = new TreeSet<String>();
set2.add("A");
set2.add("B");
set2.add("C");
txDatabase.put(2, set2);
Set<String> set3 = new TreeSet<String>();
set3.add("C");
set3.add("D");
txDatabase.put(3, set3);
Set<String> set4 = new TreeSet<String>();
set4.add("A");
set4.add("B");
set4.add("E");
txDatabase.put(4, set4);
}
/**
* 測試挖掘頻繁1-項集
*/
public void testFreq1ItemSet() {
System.out.println("挖掘頻繁1-項集 : " + apriori.getFreq1ItemSet());
}
/**
* 測試aprioriGen方法，生成候選頻繁項集
*/
public void testAprioriGen() {
System.out.println(
"候選頻繁2-項集 ： " +
this.apriori.aprioriGen(1, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 測試挖掘頻繁2-項集
*/
public void testGetFreq2ItemSet() {
System.out.println(
"挖掘頻繁2-項集 ：" +
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet())
);
}
/**
* 測試挖掘頻繁3-項集
*/
public void testGetFreq3ItemSet() {
System.out.println(
"挖掘頻繁3-項集 ：" +
this.apriori.getFreqKItemSet(
3,
this.apriori.getFreqKItemSet(2, this.apriori.getFreq1ItemSet().keySet()).keySet()
)
);
}
/**
* 測試挖掘全部頻繁項集
*/
public void testGetFreqItemSet() {
this.apriori.mineFreqItemSet(); // 挖掘頻繁項集
System.out.println("挖掘頻繁項集 ：" + this.apriori.getFreqItemSet());
}
/**
* 測試挖掘全部頻繁關聯規則
*/
public void testMineAssociationRules() {
this.apriori.mineFreqItemSet(); // 挖掘頻繁項集
this.apriori.mineAssociationRules();
System.out.println("挖掘頻繁關聯規則 ：" + this.apriori.getAssiciationRules());
}
}
測試結果：
挖掘頻繁1-項集 : {[E]=0.5, [A]=0.75, [B]=0.75, [C]=0.75}
候選頻繁2-項集 ： [[E, C], [A, B], [B, C], [A, C], [E, B], [E, A]]
挖掘頻繁2-項集 ：{[A, B]=0.75, [B, C]=0.5, [A, C]=0.5, [E, B]=0.5, [E, A]=0.5}
挖掘頻繁3-項集 ：{[E, A, B]=0.5, [A, B, C]=0.5}
挖掘頻繁項集 ：{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
挖掘頻繁關聯規則 ：{[E]=[[A], [B], [A, B]], [A]=[[B]], [B]=[[A]], [B, C]=[[A]], [A, C]=[[B]], [E, B]=[[A]], [E, A]=[[B]]}
從測試結果看到，使用Apriori演算法挖掘得到的全部頻繁項集為：
{1=[[E], [A], [B], [C]], 2=[[A, B], [B, C], [A, C], [E, B], [E, A]], 3=[[E, A, B], [A, B, C]]}
使用Apriori演算法挖掘得到的全部頻繁關聯規則為：
{E}→{A}、{E}→{B}、{E}→{A,B}、{A}→{B}、{B}→{A}、{B,C}→{A}、{A,C}→{B}、{B,E}→{A}、{A,E}→{B}。
Ⅳ 編寫程序實現演算法
#include <stdio.h>
#define false 0
#define true 1
#define maxsize 20typedef struct{
int r[maxsize+1]; //r[0]閑置或用作中轉、哨兵單元
int length;
}sqlist;void Output(sqlist &L)
{
int i;
for(i=1;i<=L.length;i++)
{
printf("%d ",L.r[i]);
}
printf("\n");
}void BubbleSort(sqlist &L) {
int i,j, Exchange;
for (i=1;i<L.length;i++){
Exchange = false;
for (j = 1; j <= L.length-i; j++)
if (L.r[j+1] < L.r[j]) {
L.r[0] =L.r[j];
L.r[j] =L.r[j+1];
L.r[j+1] =L.r[0];
Output(L);
Exchange = true;
}
if (Exchange == false) return;
}
} // BubbleSortint Partition (sqlist &L, int low, int high)
{
int pivotkey;
L.r[0]=L.r[low];
pivotkey=L.r[low];
while(low<high)
{ while(low<high&&L.r[high]>=pivotkey)--high;
L.r[low]=L.r[high];
while(low<high&&L.r[low]<=pivotkey)++low;
L.r[high]=L.r[low];
}
L.r[low]=L.r[0];
return low;
}
void QSort (sqlist &L,int low,int high)
{
int pivotloc;
if (low<high)
{pivotloc=Partition(L,low,high);Output(L); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); }
}
int main()
{
sqlist L;
int i;
scanf("%d",&L.length);
for(i=1;i<=L.length;i++)
{
scanf("%d",&L.r[i]);
}
printf("BubbleSort:\n");
BubbleSort(L);
printf("QSort:\n");
QSort(L,1,L.length);
return 0;
}
Ⅳ CUDNN入坑指南（0）卷積演算法實現類型
cuDNN目前提供以下幾種卷積演算法的實現方式 [1]
該實現方式將卷積隱式轉換成矩陣乘法，完成計算。不需要顯式將輸入張量數據轉換成矩陣形式保存。
該實現方式將卷積隱式轉換成矩陣乘法，完成計算。但是需要一些額外的內存空間去保存預計算得到的索引值，以便隱式地將輸入張量數據轉換成矩陣形式。
該實現方式將卷積顯式轉換成矩陣乘法，完成計算。在顯式完成矩陣乘法過程中，需要額外申請內存空間，將輸入轉換成矩陣形式。
該實現方式即直接完成卷積計算，不會隱式或顯式的將卷積轉換成矩陣乘法。
該實現方式利用快速傅里葉變換完成卷積計算。需要額外申請內存空間，保存中間結果。
該實現方式利用快速傅里葉變換完成卷積計算，但是需要對輸入進行分塊。同樣需要額外申請內存空間，保存中間結果，但是對大尺寸的輸入，所需內存空間小於 CUDNN_CONVOLUTION_FWD_ALGO_FFT 演算法
該實現方式利用Winograd變換完成卷積計算。需要額外申請內存空間，保存中間結果。
該實現方式利用Winograd變換完成卷積計算。需要額外申請內存空間，保存中間結果。
Ⅵ 什麼樣的演算法可以用C++類實現，什麼樣的情況適合用C實現
C++更傾向於戰略布局，設計中常用，演算法的核心實現C語言和C++基本沒有太大差別。 其實語言只是思維的一種技術實現。譬如C語言不支持面向對象，但是一樣可以實現面向對象，你看windows reactos的源碼，你就會發現，清一色的C代碼，但是用的卻是面向對象的理念。。